1 #![allow(rustc::usage_of_ty_tykind)]
3 use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
6 use crate::DebruijnIndex;
8 use crate::HashStableContext;
15 use self::RegionKind::*;
18 use rustc_data_structures::stable_hasher::HashStable;
19 use rustc_serialize::{Decodable, Decoder, Encodable};
21 /// Specifies how a trait object is represented.
36 /// An unsized `dyn Trait` object
38 /// A sized `dyn* Trait` object
40 /// These objects are represented as a `(data, vtable)` pair where `data` is a ptr-sized value
41 /// (often a pointer to the real object, but not necessarily) and `vtable` is a pointer to
42 /// the vtable for `dyn* Trait`. The representation is essentially the same as `&dyn Trait`
43 /// or similar, but the drop function included in the vtable is responsible for freeing the
44 /// underlying storage if needed. This allows a `dyn*` object to be treated agnostically with
45 /// respect to whether it points to a `Box<T>`, `Rc<T>`, etc.
49 /// Defines the kinds of types used by the type system.
51 /// Types written by the user start out as `hir::TyKind` and get
52 /// converted to this representation using `AstConv::ast_ty_to_ty`.
53 #[rustc_diagnostic_item = "IrTyKind"]
54 pub enum TyKind<I: Interner> {
55 /// The primitive boolean type. Written as `bool`.
58 /// The primitive character type; holds a Unicode scalar value
59 /// (a non-surrogate code point). Written as `char`.
62 /// A primitive signed integer type. For example, `i32`.
65 /// A primitive unsigned integer type. For example, `u32`.
68 /// A primitive floating-point type. For example, `f64`.
71 /// Algebraic data types (ADT). For example: structures, enumerations and unions.
73 /// For example, the type `List<i32>` would be represented using the `AdtDef`
74 /// for `struct List<T>` and the substs `[i32]`.
76 /// Note that generic parameters in fields only get lazily substituted
77 /// by using something like `adt_def.all_fields().map(|field| field.ty(tcx, substs))`.
78 Adt(I::AdtDef, I::SubstsRef),
80 /// An unsized FFI type that is opaque to Rust. Written as `extern type T`.
83 /// The pointee of a string slice. Written as `str`.
86 /// An array with the given length. Written as `[T; N]`.
87 Array(I::Ty, I::Const),
89 /// The pointee of an array slice. Written as `[T]`.
92 /// A raw pointer. Written as `*mut T` or `*const T`
93 RawPtr(I::TypeAndMut),
95 /// A reference; a pointer with an associated lifetime. Written as
96 /// `&'a mut T` or `&'a T`.
97 Ref(I::Region, I::Ty, I::Mutability),
99 /// The anonymous type of a function declaration/definition. Each
100 /// function has a unique type.
102 /// For the function `fn foo() -> i32 { 3 }` this type would be
103 /// shown to the user as `fn() -> i32 {foo}`.
105 /// For example the type of `bar` here:
107 /// fn foo() -> i32 { 1 }
108 /// let bar = foo; // bar: fn() -> i32 {foo}
110 FnDef(I::DefId, I::SubstsRef),
112 /// A pointer to a function. Written as `fn() -> i32`.
114 /// Note that both functions and closures start out as either
115 /// [FnDef] or [Closure] which can be then be coerced to this variant.
117 /// For example the type of `bar` here:
120 /// fn foo() -> i32 { 1 }
121 /// let bar: fn() -> i32 = foo;
125 /// A trait object. Written as `dyn for<'b> Trait<'b, Assoc = u32> + Send + 'a`.
126 Dynamic(I::ListBinderExistentialPredicate, I::Region, DynKind),
128 /// The anonymous type of a closure. Used to represent the type of `|a| a`.
130 /// Closure substs contain both the - potentially substituted - generic parameters
131 /// of its parent and some synthetic parameters. See the documentation for
132 /// `ClosureSubsts` for more details.
133 Closure(I::DefId, I::SubstsRef),
135 /// The anonymous type of a generator. Used to represent the type of
138 /// For more info about generator substs, visit the documentation for
139 /// `GeneratorSubsts`.
140 Generator(I::DefId, I::SubstsRef, I::Movability),
142 /// A type representing the types stored inside a generator.
143 /// This should only appear as part of the `GeneratorSubsts`.
145 /// Note that the captured variables for generators are stored separately
146 /// using a tuple in the same way as for closures.
148 /// Unlike upvars, the witness can reference lifetimes from
149 /// inside of the generator itself. To deal with them in
150 /// the type of the generator, we convert them to higher ranked
151 /// lifetimes bound by the witness itself.
153 /// Looking at the following example, the witness for this generator
154 /// may end up as something like `for<'a> [Vec<i32>, &'a Vec<i32>]`:
156 /// ```ignore UNSOLVED (ask @compiler-errors, should this error? can we just swap the yields?)
157 /// #![feature(generators)]
159 /// let x = &vec![3];
165 GeneratorWitness(I::BinderListTy),
167 /// The never type `!`.
170 /// A tuple type. For example, `(i32, bool)`.
173 /// The projection of an associated type. For example,
174 /// `<T as Trait<..>>::N`.
175 Projection(I::ProjectionTy),
177 /// Opaque (`impl Trait`) type found in a return type.
179 /// The `DefId` comes either from
180 /// * the `impl Trait` ast::Ty node,
181 /// * or the `type Foo = impl Trait` declaration
183 /// For RPIT the substitutions are for the generics of the function,
184 /// while for TAIT it is used for the generic parameters of the alias.
186 /// During codegen, `tcx.type_of(def_id)` can be used to get the underlying type.
187 Opaque(I::DefId, I::SubstsRef),
189 /// A type parameter; for example, `T` in `fn f<T>(x: T) {}`.
192 /// Bound type variable, used to represent the `'a` in `for<'a> fn(&'a ())`.
194 /// For canonical queries, we replace inference variables with bound variables,
195 /// so e.g. when checking whether `&'_ (): Trait<_>` holds, we canonicalize that to
196 /// `for<'a, T> &'a (): Trait<T>` and then convert the introduced bound variables
197 /// back to inference variables in a new inference context when inside of the query.
199 /// See the `rustc-dev-guide` for more details about
200 /// [higher-ranked trait bounds][1] and [canonical queries][2].
202 /// [1]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
203 /// [2]: https://rustc-dev-guide.rust-lang.org/traits/canonical-queries.html
204 Bound(DebruijnIndex, I::BoundTy),
206 /// A placeholder type, used during higher ranked subtyping to instantiate
208 Placeholder(I::PlaceholderType),
210 /// A type variable used during type checking.
212 /// Similar to placeholders, inference variables also live in a universe to
213 /// correctly deal with higher ranked types. Though unlike placeholders,
214 /// that universe is stored in the `InferCtxt` instead of directly
215 /// inside of the type.
218 /// A placeholder for a type which could not be computed; this is
219 /// propagated to avoid useless error messages.
220 Error(I::ErrorGuaranteed),
223 impl<I: Interner> TyKind<I> {
225 pub fn is_primitive(&self) -> bool {
226 matches!(self, Bool | Char | Int(_) | Uint(_) | Float(_))
230 // This is manually implemented for `TyKind` because `std::mem::discriminant`
231 // returns an opaque value that is `PartialEq` but not `PartialOrd`
233 const fn tykind_discriminant<I: Interner>(value: &TyKind<I>) -> usize {
251 Generator(_, _, _) => 16,
252 GeneratorWitness(_) => 17,
259 Placeholder(_) => 24,
265 // This is manually implemented because a derive would require `I: Clone`
266 impl<I: Interner> Clone for TyKind<I> {
267 fn clone(&self) -> Self {
271 Int(i) => Int(i.clone()),
272 Uint(u) => Uint(u.clone()),
273 Float(f) => Float(f.clone()),
274 Adt(d, s) => Adt(d.clone(), s.clone()),
275 Foreign(d) => Foreign(d.clone()),
277 Array(t, c) => Array(t.clone(), c.clone()),
278 Slice(t) => Slice(t.clone()),
279 RawPtr(t) => RawPtr(t.clone()),
280 Ref(r, t, m) => Ref(r.clone(), t.clone(), m.clone()),
281 FnDef(d, s) => FnDef(d.clone(), s.clone()),
282 FnPtr(s) => FnPtr(s.clone()),
283 Dynamic(p, r, repr) => Dynamic(p.clone(), r.clone(), repr.clone()),
284 Closure(d, s) => Closure(d.clone(), s.clone()),
285 Generator(d, s, m) => Generator(d.clone(), s.clone(), m.clone()),
286 GeneratorWitness(g) => GeneratorWitness(g.clone()),
288 Tuple(t) => Tuple(t.clone()),
289 Projection(p) => Projection(p.clone()),
290 Opaque(d, s) => Opaque(d.clone(), s.clone()),
291 Param(p) => Param(p.clone()),
292 Bound(d, b) => Bound(d.clone(), b.clone()),
293 Placeholder(p) => Placeholder(p.clone()),
294 Infer(t) => Infer(t.clone()),
295 Error(e) => Error(e.clone()),
300 // This is manually implemented because a derive would require `I: PartialEq`
301 impl<I: Interner> PartialEq for TyKind<I> {
303 fn eq(&self, other: &TyKind<I>) -> bool {
304 tykind_discriminant(self) == tykind_discriminant(other)
305 && match (self, other) {
306 (Int(a_i), Int(b_i)) => a_i == b_i,
307 (Uint(a_u), Uint(b_u)) => a_u == b_u,
308 (Float(a_f), Float(b_f)) => a_f == b_f,
309 (Adt(a_d, a_s), Adt(b_d, b_s)) => a_d == b_d && a_s == b_s,
310 (Foreign(a_d), Foreign(b_d)) => a_d == b_d,
311 (Array(a_t, a_c), Array(b_t, b_c)) => a_t == b_t && a_c == b_c,
312 (Slice(a_t), Slice(b_t)) => a_t == b_t,
313 (RawPtr(a_t), RawPtr(b_t)) => a_t == b_t,
314 (Ref(a_r, a_t, a_m), Ref(b_r, b_t, b_m)) => a_r == b_r && a_t == b_t && a_m == b_m,
315 (FnDef(a_d, a_s), FnDef(b_d, b_s)) => a_d == b_d && a_s == b_s,
316 (FnPtr(a_s), FnPtr(b_s)) => a_s == b_s,
317 (Dynamic(a_p, a_r, a_repr), Dynamic(b_p, b_r, b_repr)) => {
318 a_p == b_p && a_r == b_r && a_repr == b_repr
320 (Closure(a_d, a_s), Closure(b_d, b_s)) => a_d == b_d && a_s == b_s,
321 (Generator(a_d, a_s, a_m), Generator(b_d, b_s, b_m)) => {
322 a_d == b_d && a_s == b_s && a_m == b_m
324 (GeneratorWitness(a_g), GeneratorWitness(b_g)) => a_g == b_g,
325 (Tuple(a_t), Tuple(b_t)) => a_t == b_t,
326 (Projection(a_p), Projection(b_p)) => a_p == b_p,
327 (Opaque(a_d, a_s), Opaque(b_d, b_s)) => a_d == b_d && a_s == b_s,
328 (Param(a_p), Param(b_p)) => a_p == b_p,
329 (Bound(a_d, a_b), Bound(b_d, b_b)) => a_d == b_d && a_b == b_b,
330 (Placeholder(a_p), Placeholder(b_p)) => a_p == b_p,
331 (Infer(a_t), Infer(b_t)) => a_t == b_t,
332 (Error(a_e), Error(b_e)) => a_e == b_e,
333 (Bool, Bool) | (Char, Char) | (Str, Str) | (Never, Never) => true,
337 "This branch must be unreachable, maybe the match is missing an arm? self = self = {self:?}, other = {other:?}"
345 // This is manually implemented because a derive would require `I: Eq`
346 impl<I: Interner> Eq for TyKind<I> {}
348 // This is manually implemented because a derive would require `I: PartialOrd`
349 impl<I: Interner> PartialOrd for TyKind<I> {
351 fn partial_cmp(&self, other: &TyKind<I>) -> Option<Ordering> {
352 Some(self.cmp(other))
356 // This is manually implemented because a derive would require `I: Ord`
357 impl<I: Interner> Ord for TyKind<I> {
359 fn cmp(&self, other: &TyKind<I>) -> Ordering {
360 tykind_discriminant(self).cmp(&tykind_discriminant(other)).then_with(|| {
361 match (self, other) {
362 (Int(a_i), Int(b_i)) => a_i.cmp(b_i),
363 (Uint(a_u), Uint(b_u)) => a_u.cmp(b_u),
364 (Float(a_f), Float(b_f)) => a_f.cmp(b_f),
365 (Adt(a_d, a_s), Adt(b_d, b_s)) => a_d.cmp(b_d).then_with(|| a_s.cmp(b_s)),
366 (Foreign(a_d), Foreign(b_d)) => a_d.cmp(b_d),
367 (Array(a_t, a_c), Array(b_t, b_c)) => a_t.cmp(b_t).then_with(|| a_c.cmp(b_c)),
368 (Slice(a_t), Slice(b_t)) => a_t.cmp(b_t),
369 (RawPtr(a_t), RawPtr(b_t)) => a_t.cmp(b_t),
370 (Ref(a_r, a_t, a_m), Ref(b_r, b_t, b_m)) => {
371 a_r.cmp(b_r).then_with(|| a_t.cmp(b_t).then_with(|| a_m.cmp(b_m)))
373 (FnDef(a_d, a_s), FnDef(b_d, b_s)) => a_d.cmp(b_d).then_with(|| a_s.cmp(b_s)),
374 (FnPtr(a_s), FnPtr(b_s)) => a_s.cmp(b_s),
375 (Dynamic(a_p, a_r, a_repr), Dynamic(b_p, b_r, b_repr)) => {
376 a_p.cmp(b_p).then_with(|| a_r.cmp(b_r).then_with(|| a_repr.cmp(b_repr)))
378 (Closure(a_p, a_s), Closure(b_p, b_s)) => a_p.cmp(b_p).then_with(|| a_s.cmp(b_s)),
379 (Generator(a_d, a_s, a_m), Generator(b_d, b_s, b_m)) => {
380 a_d.cmp(b_d).then_with(|| a_s.cmp(b_s).then_with(|| a_m.cmp(b_m)))
382 (GeneratorWitness(a_g), GeneratorWitness(b_g)) => a_g.cmp(b_g),
383 (Tuple(a_t), Tuple(b_t)) => a_t.cmp(b_t),
384 (Projection(a_p), Projection(b_p)) => a_p.cmp(b_p),
385 (Opaque(a_d, a_s), Opaque(b_d, b_s)) => a_d.cmp(b_d).then_with(|| a_s.cmp(b_s)),
386 (Param(a_p), Param(b_p)) => a_p.cmp(b_p),
387 (Bound(a_d, a_b), Bound(b_d, b_b)) => a_d.cmp(b_d).then_with(|| a_b.cmp(b_b)),
388 (Placeholder(a_p), Placeholder(b_p)) => a_p.cmp(b_p),
389 (Infer(a_t), Infer(b_t)) => a_t.cmp(b_t),
390 (Error(a_e), Error(b_e)) => a_e.cmp(b_e),
391 (Bool, Bool) | (Char, Char) | (Str, Str) | (Never, Never) => Ordering::Equal,
393 debug_assert!(false, "This branch must be unreachable, maybe the match is missing an arm? self = self = {self:?}, other = {other:?}");
401 // This is manually implemented because a derive would require `I: Hash`
402 impl<I: Interner> hash::Hash for TyKind<I> {
403 fn hash<__H: hash::Hasher>(&self, state: &mut __H) -> () {
404 tykind_discriminant(self).hash(state);
406 Int(i) => i.hash(state),
407 Uint(u) => u.hash(state),
408 Float(f) => f.hash(state),
413 Foreign(d) => d.hash(state),
418 Slice(t) => t.hash(state),
419 RawPtr(t) => t.hash(state),
429 FnPtr(s) => s.hash(state),
430 Dynamic(p, r, repr) => {
439 Generator(d, s, m) => {
444 GeneratorWitness(g) => g.hash(state),
445 Tuple(t) => t.hash(state),
446 Projection(p) => p.hash(state),
451 Param(p) => p.hash(state),
456 Placeholder(p) => p.hash(state),
457 Infer(t) => t.hash(state),
458 Error(e) => e.hash(state),
459 Bool | Char | Str | Never => (),
464 // This is manually implemented because a derive would require `I: Debug`
465 impl<I: Interner> fmt::Debug for TyKind<I> {
466 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
468 Bool => f.write_str("Bool"),
469 Char => f.write_str("Char"),
470 Int(i) => f.debug_tuple_field1_finish("Int", i),
471 Uint(u) => f.debug_tuple_field1_finish("Uint", u),
472 Float(float) => f.debug_tuple_field1_finish("Float", float),
473 Adt(d, s) => f.debug_tuple_field2_finish("Adt", d, s),
474 Foreign(d) => f.debug_tuple_field1_finish("Foreign", d),
475 Str => f.write_str("Str"),
476 Array(t, c) => f.debug_tuple_field2_finish("Array", t, c),
477 Slice(t) => f.debug_tuple_field1_finish("Slice", t),
478 RawPtr(t) => f.debug_tuple_field1_finish("RawPtr", t),
479 Ref(r, t, m) => f.debug_tuple_field3_finish("Ref", r, t, m),
480 FnDef(d, s) => f.debug_tuple_field2_finish("FnDef", d, s),
481 FnPtr(s) => f.debug_tuple_field1_finish("FnPtr", s),
482 Dynamic(p, r, repr) => f.debug_tuple_field3_finish("Dynamic", p, r, repr),
483 Closure(d, s) => f.debug_tuple_field2_finish("Closure", d, s),
484 Generator(d, s, m) => f.debug_tuple_field3_finish("Generator", d, s, m),
485 GeneratorWitness(g) => f.debug_tuple_field1_finish("GeneratorWitness", g),
486 Never => f.write_str("Never"),
487 Tuple(t) => f.debug_tuple_field1_finish("Tuple", t),
488 Projection(p) => f.debug_tuple_field1_finish("Projection", p),
489 Opaque(d, s) => f.debug_tuple_field2_finish("Opaque", d, s),
490 Param(p) => f.debug_tuple_field1_finish("Param", p),
491 Bound(d, b) => f.debug_tuple_field2_finish("Bound", d, b),
492 Placeholder(p) => f.debug_tuple_field1_finish("Placeholder", p),
493 Infer(t) => f.debug_tuple_field1_finish("Infer", t),
494 TyKind::Error(e) => f.debug_tuple_field1_finish("Error", e),
499 // This is manually implemented because a derive would require `I: Encodable`
500 impl<I: Interner, E: TyEncoder> Encodable<E> for TyKind<I>
502 I::ErrorGuaranteed: Encodable<E>,
503 I::AdtDef: Encodable<E>,
504 I::SubstsRef: Encodable<E>,
505 I::DefId: Encodable<E>,
507 I::Const: Encodable<E>,
508 I::Region: Encodable<E>,
509 I::TypeAndMut: Encodable<E>,
510 I::Mutability: Encodable<E>,
511 I::Movability: Encodable<E>,
512 I::PolyFnSig: Encodable<E>,
513 I::ListBinderExistentialPredicate: Encodable<E>,
514 I::BinderListTy: Encodable<E>,
515 I::ListTy: Encodable<E>,
516 I::ProjectionTy: Encodable<E>,
517 I::ParamTy: Encodable<E>,
518 I::BoundTy: Encodable<E>,
519 I::PlaceholderType: Encodable<E>,
520 I::InferTy: Encodable<E>,
521 I::PredicateKind: Encodable<E>,
522 I::AllocId: Encodable<E>,
524 fn encode(&self, e: &mut E) {
525 let disc = tykind_discriminant(self);
527 Bool => e.emit_enum_variant(disc, |_| {}),
528 Char => e.emit_enum_variant(disc, |_| {}),
529 Int(i) => e.emit_enum_variant(disc, |e| {
532 Uint(u) => e.emit_enum_variant(disc, |e| {
535 Float(f) => e.emit_enum_variant(disc, |e| {
538 Adt(adt, substs) => e.emit_enum_variant(disc, |e| {
542 Foreign(def_id) => e.emit_enum_variant(disc, |e| {
545 Str => e.emit_enum_variant(disc, |_| {}),
546 Array(t, c) => e.emit_enum_variant(disc, |e| {
550 Slice(t) => e.emit_enum_variant(disc, |e| {
553 RawPtr(tam) => e.emit_enum_variant(disc, |e| {
556 Ref(r, t, m) => e.emit_enum_variant(disc, |e| {
561 FnDef(def_id, substs) => e.emit_enum_variant(disc, |e| {
565 FnPtr(polyfnsig) => e.emit_enum_variant(disc, |e| {
568 Dynamic(l, r, repr) => e.emit_enum_variant(disc, |e| {
573 Closure(def_id, substs) => e.emit_enum_variant(disc, |e| {
577 Generator(def_id, substs, m) => e.emit_enum_variant(disc, |e| {
582 GeneratorWitness(b) => e.emit_enum_variant(disc, |e| {
585 Never => e.emit_enum_variant(disc, |_| {}),
586 Tuple(substs) => e.emit_enum_variant(disc, |e| {
589 Projection(p) => e.emit_enum_variant(disc, |e| {
592 Opaque(def_id, substs) => e.emit_enum_variant(disc, |e| {
596 Param(p) => e.emit_enum_variant(disc, |e| {
599 Bound(d, b) => e.emit_enum_variant(disc, |e| {
603 Placeholder(p) => e.emit_enum_variant(disc, |e| {
606 Infer(i) => e.emit_enum_variant(disc, |e| {
609 Error(d) => e.emit_enum_variant(disc, |e| {
616 // This is manually implemented because a derive would require `I: Decodable`
617 impl<I: Interner, D: TyDecoder<I = I>> Decodable<D> for TyKind<I>
619 I::ErrorGuaranteed: Decodable<D>,
620 I::AdtDef: Decodable<D>,
621 I::SubstsRef: Decodable<D>,
622 I::DefId: Decodable<D>,
624 I::Const: Decodable<D>,
625 I::Region: Decodable<D>,
626 I::TypeAndMut: Decodable<D>,
627 I::Mutability: Decodable<D>,
628 I::Movability: Decodable<D>,
629 I::PolyFnSig: Decodable<D>,
630 I::ListBinderExistentialPredicate: Decodable<D>,
631 I::BinderListTy: Decodable<D>,
632 I::ListTy: Decodable<D>,
633 I::ProjectionTy: Decodable<D>,
634 I::ParamTy: Decodable<D>,
635 I::BoundTy: Decodable<D>,
636 I::PlaceholderType: Decodable<D>,
637 I::InferTy: Decodable<D>,
638 I::PredicateKind: Decodable<D>,
639 I::AllocId: Decodable<D>,
641 fn decode(d: &mut D) -> Self {
642 match Decoder::read_usize(d) {
645 2 => Int(Decodable::decode(d)),
646 3 => Uint(Decodable::decode(d)),
647 4 => Float(Decodable::decode(d)),
648 5 => Adt(Decodable::decode(d), Decodable::decode(d)),
649 6 => Foreign(Decodable::decode(d)),
651 8 => Array(Decodable::decode(d), Decodable::decode(d)),
652 9 => Slice(Decodable::decode(d)),
653 10 => RawPtr(Decodable::decode(d)),
654 11 => Ref(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)),
655 12 => FnDef(Decodable::decode(d), Decodable::decode(d)),
656 13 => FnPtr(Decodable::decode(d)),
657 14 => Dynamic(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)),
658 15 => Closure(Decodable::decode(d), Decodable::decode(d)),
659 16 => Generator(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)),
660 17 => GeneratorWitness(Decodable::decode(d)),
662 19 => Tuple(Decodable::decode(d)),
663 20 => Projection(Decodable::decode(d)),
664 21 => Opaque(Decodable::decode(d), Decodable::decode(d)),
665 22 => Param(Decodable::decode(d)),
666 23 => Bound(Decodable::decode(d), Decodable::decode(d)),
667 24 => Placeholder(Decodable::decode(d)),
668 25 => Infer(Decodable::decode(d)),
669 26 => Error(Decodable::decode(d)),
673 "invalid enum variant tag while decoding `{}`, expected 0..{}",
681 // This is not a derived impl because a derive would require `I: HashStable`
682 #[allow(rustc::usage_of_ty_tykind)]
683 impl<CTX: HashStableContext, I: Interner> HashStable<CTX> for TyKind<I>
685 I::AdtDef: HashStable<CTX>,
686 I::DefId: HashStable<CTX>,
687 I::SubstsRef: HashStable<CTX>,
688 I::Ty: HashStable<CTX>,
689 I::Const: HashStable<CTX>,
690 I::TypeAndMut: HashStable<CTX>,
691 I::PolyFnSig: HashStable<CTX>,
692 I::ListBinderExistentialPredicate: HashStable<CTX>,
693 I::Region: HashStable<CTX>,
694 I::Movability: HashStable<CTX>,
695 I::Mutability: HashStable<CTX>,
696 I::BinderListTy: HashStable<CTX>,
697 I::ListTy: HashStable<CTX>,
698 I::ProjectionTy: HashStable<CTX>,
699 I::BoundTy: HashStable<CTX>,
700 I::ParamTy: HashStable<CTX>,
701 I::PlaceholderType: HashStable<CTX>,
702 I::InferTy: HashStable<CTX>,
703 I::ErrorGuaranteed: HashStable<CTX>,
709 __hasher: &mut rustc_data_structures::stable_hasher::StableHasher,
711 std::mem::discriminant(self).hash_stable(__hcx, __hasher);
716 i.hash_stable(__hcx, __hasher);
719 u.hash_stable(__hcx, __hasher);
722 f.hash_stable(__hcx, __hasher);
724 Adt(adt, substs) => {
725 adt.hash_stable(__hcx, __hasher);
726 substs.hash_stable(__hcx, __hasher);
729 def_id.hash_stable(__hcx, __hasher);
733 t.hash_stable(__hcx, __hasher);
734 c.hash_stable(__hcx, __hasher);
737 t.hash_stable(__hcx, __hasher);
740 tam.hash_stable(__hcx, __hasher);
743 r.hash_stable(__hcx, __hasher);
744 t.hash_stable(__hcx, __hasher);
745 m.hash_stable(__hcx, __hasher);
747 FnDef(def_id, substs) => {
748 def_id.hash_stable(__hcx, __hasher);
749 substs.hash_stable(__hcx, __hasher);
751 FnPtr(polyfnsig) => {
752 polyfnsig.hash_stable(__hcx, __hasher);
754 Dynamic(l, r, repr) => {
755 l.hash_stable(__hcx, __hasher);
756 r.hash_stable(__hcx, __hasher);
757 repr.hash_stable(__hcx, __hasher);
759 Closure(def_id, substs) => {
760 def_id.hash_stable(__hcx, __hasher);
761 substs.hash_stable(__hcx, __hasher);
763 Generator(def_id, substs, m) => {
764 def_id.hash_stable(__hcx, __hasher);
765 substs.hash_stable(__hcx, __hasher);
766 m.hash_stable(__hcx, __hasher);
768 GeneratorWitness(b) => {
769 b.hash_stable(__hcx, __hasher);
773 substs.hash_stable(__hcx, __hasher);
776 p.hash_stable(__hcx, __hasher);
778 Opaque(def_id, substs) => {
779 def_id.hash_stable(__hcx, __hasher);
780 substs.hash_stable(__hcx, __hasher);
783 p.hash_stable(__hcx, __hasher);
786 d.hash_stable(__hcx, __hasher);
787 b.hash_stable(__hcx, __hasher);
790 p.hash_stable(__hcx, __hasher);
793 i.hash_stable(__hcx, __hasher);
796 d.hash_stable(__hcx, __hasher);
802 /// Representation of regions. Note that the NLL checker uses a distinct
803 /// representation of regions. For this reason, it internally replaces all the
804 /// regions with inference variables -- the index of the variable is then used
805 /// to index into internal NLL data structures. See `rustc_const_eval::borrow_check`
806 /// module for more information.
808 /// Note: operations are on the wrapper `Region` type, which is interned,
809 /// rather than this type.
811 /// ## The Region lattice within a given function
813 /// In general, the region lattice looks like
816 /// static ----------+-----...------+ (greatest)
818 /// early-bound and | |
822 /// empty(root) placeholder(U1) |
824 /// | / placeholder(Un)
829 /// empty(Un) -------- (smallest)
832 /// Early-bound/free regions are the named lifetimes in scope from the
833 /// function declaration. They have relationships to one another
834 /// determined based on the declared relationships from the
837 /// Note that inference variables and bound regions are not included
838 /// in this diagram. In the case of inference variables, they should
839 /// be inferred to some other region from the diagram. In the case of
840 /// bound regions, they are excluded because they don't make sense to
841 /// include -- the diagram indicates the relationship between free
844 /// ## Inference variables
846 /// During region inference, we sometimes create inference variables,
847 /// represented as `ReVar`. These will be inferred by the code in
848 /// `infer::lexical_region_resolve` to some free region from the
849 /// lattice above (the minimal region that meets the
852 /// During NLL checking, where regions are defined differently, we
853 /// also use `ReVar` -- in that case, the index is used to index into
854 /// the NLL region checker's data structures. The variable may in fact
855 /// represent either a free region or an inference variable, in that
860 /// These are regions that are stored behind a binder and must be substituted
861 /// with some concrete region before being used. There are two kind of
862 /// bound regions: early-bound, which are bound in an item's `Generics`,
863 /// and are substituted by an `InternalSubsts`, and late-bound, which are part of
864 /// higher-ranked types (e.g., `for<'a> fn(&'a ())`), and are substituted by
865 /// the likes of `liberate_late_bound_regions`. The distinction exists
866 /// because higher-ranked lifetimes aren't supported in all places. See [1][2].
868 /// Unlike `Param`s, bound regions are not supposed to exist "in the wild"
869 /// outside their binder, e.g., in types passed to type inference, and
870 /// should first be substituted (by placeholder regions, free regions,
871 /// or region variables).
873 /// ## Placeholder and Free Regions
875 /// One often wants to work with bound regions without knowing their precise
876 /// identity. For example, when checking a function, the lifetime of a borrow
877 /// can end up being assigned to some region parameter. In these cases,
878 /// it must be ensured that bounds on the region can't be accidentally
879 /// assumed without being checked.
881 /// To do this, we replace the bound regions with placeholder markers,
882 /// which don't satisfy any relation not explicitly provided.
884 /// There are two kinds of placeholder regions in rustc: `ReFree` and
885 /// `RePlaceholder`. When checking an item's body, `ReFree` is supposed
886 /// to be used. These also support explicit bounds: both the internally-stored
887 /// *scope*, which the region is assumed to outlive, as well as other
888 /// relations stored in the `FreeRegionMap`. Note that these relations
889 /// aren't checked when you `make_subregion` (or `eq_types`), only by
890 /// `resolve_regions_and_report_errors`.
892 /// When working with higher-ranked types, some region relations aren't
893 /// yet known, so you can't just call `resolve_regions_and_report_errors`.
894 /// `RePlaceholder` is designed for this purpose. In these contexts,
895 /// there's also the risk that some inference variable laying around will
896 /// get unified with your placeholder region: if you want to check whether
897 /// `for<'a> Foo<'_>: 'a`, and you substitute your bound region `'a`
898 /// with a placeholder region `'%a`, the variable `'_` would just be
899 /// instantiated to the placeholder region `'%a`, which is wrong because
900 /// the inference variable is supposed to satisfy the relation
901 /// *for every value of the placeholder region*. To ensure that doesn't
902 /// happen, you can use `leak_check`. This is more clearly explained
903 /// by the [rustc dev guide].
905 /// [1]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
906 /// [2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
907 /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
908 pub enum RegionKind<I: Interner> {
909 /// Region bound in a type or fn declaration which will be
910 /// substituted 'early' -- that is, at the same time when type
911 /// parameters are substituted.
912 ReEarlyBound(I::EarlyBoundRegion),
914 /// Region bound in a function scope, which will be substituted when the
915 /// function is called.
916 ReLateBound(DebruijnIndex, I::BoundRegion),
918 /// When checking a function body, the types of all arguments and so forth
919 /// that refer to bound region parameters are modified to refer to free
920 /// region parameters.
921 ReFree(I::FreeRegion),
923 /// Static data that has an "infinite" lifetime. Top in the region lattice.
926 /// A region variable. Should not exist outside of type inference.
929 /// A placeholder region -- basically, the higher-ranked version of `ReFree`.
930 /// Should not exist outside of type inference.
931 RePlaceholder(I::PlaceholderRegion),
933 /// Erased region, used by trait selection, in MIR and during codegen.
937 // This is manually implemented for `RegionKind` because `std::mem::discriminant`
938 // returns an opaque value that is `PartialEq` but not `PartialOrd`
940 const fn regionkind_discriminant<I: Interner>(value: &RegionKind<I>) -> usize {
942 ReEarlyBound(_) => 0,
943 ReLateBound(_, _) => 1,
947 RePlaceholder(_) => 5,
952 // This is manually implemented because a derive would require `I: Copy`
953 impl<I: Interner> Copy for RegionKind<I>
955 I::EarlyBoundRegion: Copy,
956 I::BoundRegion: Copy,
959 I::PlaceholderRegion: Copy,
963 // This is manually implemented because a derive would require `I: Clone`
964 impl<I: Interner> Clone for RegionKind<I> {
965 fn clone(&self) -> Self {
967 ReEarlyBound(r) => ReEarlyBound(r.clone()),
968 ReLateBound(d, r) => ReLateBound(d.clone(), r.clone()),
969 ReFree(r) => ReFree(r.clone()),
970 ReStatic => ReStatic,
971 ReVar(r) => ReVar(r.clone()),
972 RePlaceholder(r) => RePlaceholder(r.clone()),
973 ReErased => ReErased,
978 // This is manually implemented because a derive would require `I: PartialEq`
979 impl<I: Interner> PartialEq for RegionKind<I> {
981 fn eq(&self, other: &RegionKind<I>) -> bool {
982 regionkind_discriminant(self) == regionkind_discriminant(other)
983 && match (self, other) {
984 (ReEarlyBound(a_r), ReEarlyBound(b_r)) => a_r == b_r,
985 (ReLateBound(a_d, a_r), ReLateBound(b_d, b_r)) => a_d == b_d && a_r == b_r,
986 (ReFree(a_r), ReFree(b_r)) => a_r == b_r,
987 (ReStatic, ReStatic) => true,
988 (ReVar(a_r), ReVar(b_r)) => a_r == b_r,
989 (RePlaceholder(a_r), RePlaceholder(b_r)) => a_r == b_r,
990 (ReErased, ReErased) => true,
994 "This branch must be unreachable, maybe the match is missing an arm? self = self = {self:?}, other = {other:?}"
1002 // This is manually implemented because a derive would require `I: Eq`
1003 impl<I: Interner> Eq for RegionKind<I> {}
1005 // This is manually implemented because a derive would require `I: PartialOrd`
1006 impl<I: Interner> PartialOrd for RegionKind<I> {
1008 fn partial_cmp(&self, other: &RegionKind<I>) -> Option<Ordering> {
1009 Some(self.cmp(other))
1013 // This is manually implemented because a derive would require `I: Ord`
1014 impl<I: Interner> Ord for RegionKind<I> {
1016 fn cmp(&self, other: &RegionKind<I>) -> Ordering {
1017 regionkind_discriminant(self).cmp(®ionkind_discriminant(other)).then_with(|| {
1018 match (self, other) {
1019 (ReEarlyBound(a_r), ReEarlyBound(b_r)) => a_r.cmp(b_r),
1020 (ReLateBound(a_d, a_r), ReLateBound(b_d, b_r)) => {
1021 a_d.cmp(b_d).then_with(|| a_r.cmp(b_r))
1023 (ReFree(a_r), ReFree(b_r)) => a_r.cmp(b_r),
1024 (ReStatic, ReStatic) => Ordering::Equal,
1025 (ReVar(a_r), ReVar(b_r)) => a_r.cmp(b_r),
1026 (RePlaceholder(a_r), RePlaceholder(b_r)) => a_r.cmp(b_r),
1027 (ReErased, ReErased) => Ordering::Equal,
1029 debug_assert!(false, "This branch must be unreachable, maybe the match is missing an arm? self = self = {self:?}, other = {other:?}");
1037 // This is manually implemented because a derive would require `I: Hash`
1038 impl<I: Interner> hash::Hash for RegionKind<I> {
1039 fn hash<H: hash::Hasher>(&self, state: &mut H) -> () {
1040 regionkind_discriminant(self).hash(state);
1042 ReEarlyBound(r) => r.hash(state),
1043 ReLateBound(d, r) => {
1047 ReFree(r) => r.hash(state),
1049 ReVar(r) => r.hash(state),
1050 RePlaceholder(r) => r.hash(state),
1056 // This is manually implemented because a derive would require `I: Debug`
1057 impl<I: Interner> fmt::Debug for RegionKind<I> {
1058 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1060 ReEarlyBound(data) => write!(f, "ReEarlyBound({:?})", data),
1062 ReLateBound(binder_id, bound_region) => {
1063 write!(f, "ReLateBound({:?}, {:?})", binder_id, bound_region)
1066 ReFree(fr) => fr.fmt(f),
1068 ReStatic => f.write_str("ReStatic"),
1070 ReVar(vid) => vid.fmt(f),
1072 RePlaceholder(placeholder) => write!(f, "RePlaceholder({:?})", placeholder),
1074 ReErased => f.write_str("ReErased"),
1079 // This is manually implemented because a derive would require `I: Encodable`
1080 impl<I: Interner, E: TyEncoder> Encodable<E> for RegionKind<I>
1082 I::EarlyBoundRegion: Encodable<E>,
1083 I::BoundRegion: Encodable<E>,
1084 I::FreeRegion: Encodable<E>,
1085 I::RegionVid: Encodable<E>,
1086 I::PlaceholderRegion: Encodable<E>,
1088 fn encode(&self, e: &mut E) {
1089 let disc = regionkind_discriminant(self);
1091 ReEarlyBound(a) => e.emit_enum_variant(disc, |e| {
1094 ReLateBound(a, b) => e.emit_enum_variant(disc, |e| {
1098 ReFree(a) => e.emit_enum_variant(disc, |e| {
1101 ReStatic => e.emit_enum_variant(disc, |_| {}),
1102 ReVar(a) => e.emit_enum_variant(disc, |e| {
1105 RePlaceholder(a) => e.emit_enum_variant(disc, |e| {
1108 ReErased => e.emit_enum_variant(disc, |_| {}),
1113 // This is manually implemented because a derive would require `I: Decodable`
1114 impl<I: Interner, D: TyDecoder<I = I>> Decodable<D> for RegionKind<I>
1116 I::EarlyBoundRegion: Decodable<D>,
1117 I::BoundRegion: Decodable<D>,
1118 I::FreeRegion: Decodable<D>,
1119 I::RegionVid: Decodable<D>,
1120 I::PlaceholderRegion: Decodable<D>,
1122 fn decode(d: &mut D) -> Self {
1123 match Decoder::read_usize(d) {
1124 0 => ReEarlyBound(Decodable::decode(d)),
1125 1 => ReLateBound(Decodable::decode(d), Decodable::decode(d)),
1126 2 => ReFree(Decodable::decode(d)),
1128 4 => ReVar(Decodable::decode(d)),
1129 5 => RePlaceholder(Decodable::decode(d)),
1134 "invalid enum variant tag while decoding `{}`, expected 0..{}",
1142 // This is not a derived impl because a derive would require `I: HashStable`
1143 impl<CTX: HashStableContext, I: Interner> HashStable<CTX> for RegionKind<I>
1145 I::EarlyBoundRegion: HashStable<CTX>,
1146 I::BoundRegion: HashStable<CTX>,
1147 I::FreeRegion: HashStable<CTX>,
1148 I::RegionVid: HashStable<CTX>,
1149 I::PlaceholderRegion: HashStable<CTX>,
1155 hasher: &mut rustc_data_structures::stable_hasher::StableHasher,
1157 std::mem::discriminant(self).hash_stable(hcx, hasher);
1159 ReErased | ReStatic => {
1160 // No variant fields to hash for these ...
1162 ReLateBound(d, r) => {
1163 d.hash_stable(hcx, hasher);
1164 r.hash_stable(hcx, hasher);
1166 ReEarlyBound(r) => {
1167 r.hash_stable(hcx, hasher);
1170 r.hash_stable(hcx, hasher);
1172 RePlaceholder(r) => {
1173 r.hash_stable(hcx, hasher);
1176 panic!("region variables should not be hashed: {self:?}")