1#![cfg_attr(feature = "nightly", rustc_diagnostic_item = "type_ir")]
2// tidy-alphabetical-start
3#![allow(rustc::direct_use_of_rustc_type_ir)]
4#![allow(rustc::usage_of_ty_tykind)]
5#![allow(rustc::usage_of_type_ir_inherent)]
6#![allow(rustc::usage_of_type_ir_traits)]
7#![cfg_attr(feature = "nightly", allow(internal_features))]
8#![cfg_attr(feature = "nightly", feature(associated_type_defaults, rustc_attrs, negative_impls))]
9// tidy-alphabetical-end
1011extern crate self as rustc_type_ir;
1213use std::fmt;
14use std::hash::Hash;
1516use rustc_abi::{FieldIdx, VariantIdx};
17#[cfg(feature = "nightly")]
18use rustc_macros::{Decodable, Encodable, StableHash};
1920// These modules are `pub` since they are not glob-imported.
21pub mod data_structures;
22pub mod elaborate;
23pub mod error;
24pub mod fast_reject;
25#[cfg_attr(feature = "nightly", rustc_diagnostic_item = "type_ir_inherent")]
26pub mod inherent;
27pub mod intern;
28pub mod ir_print;
29pub mod lang_items;
30pub mod lift;
31pub mod outlives;
32pub mod region_constraint;
33pub mod relate;
34pub mod search_graph;
35pub mod solve;
36pub mod sty;
37pub mod walk;
3839// These modules are not `pub` since they are glob-imported.
40#[macro_use]
41mod macros;
42mod binder;
43mod canonical;
44mod const_kind;
45mod flags;
46mod fold;
47mod generic_arg;
48#[cfg(not(feature = "nightly"))]
49mod generic_visit;
50mod infer_ctxt;
51mod interner;
52mod opaque_ty;
53mod pattern;
54mod predicate;
55mod predicate_kind;
56mod region_kind;
57#[cfg(feature = "nightly")]
58mod serialize;
59mod term_kind;
60mod ty;
61mod ty_info;
62mod ty_kind;
63mod universe;
64mod unnormalized;
65mod upcast;
66mod visit;
6768pub use AliasTyKind::*;
69pub use InferTy::*;
70pub use RegionKind::*;
71pub use TyKind::*;
72pub use Variance::*;
73pub use binder::{Placeholder, *};
74pub use canonical::*;
75pub use const_kind::*;
76pub use flags::*;
77pub use fold::*;
78pub use generic_arg::*;
79#[cfg(not(feature = "nightly"))]
80pub use generic_visit::*;
81pub use infer_ctxt::*;
82pub use interner::*;
83pub use opaque_ty::*;
84pub use pattern::*;
85pub use predicate::*;
86pub use predicate_kind::*;
87pub use region_kind::*;
88pub use rustc_ast_ir::{FloatTy, IntTy, Movability, Mutability, Pinnedness, UintTy};
89use rustc_type_ir_macros::GenericTypeVisitable;
90#[cfg(feature = "nightly")]
91pub use serialize::*;
92pub use sty::*;
93pub use term_kind::*;
94pub use ty::{Alias, *};
95pub use ty_info::*;
96pub use ty_kind::*;
97pub use universe::*;
98pub use unnormalized::Unnormalized;
99pub use upcast::*;
100pub use visit::*;
101102impl ::std::fmt::Debug for DebruijnIndex {
fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
fmt.write_fmt(format_args!("DebruijnIndex({0})", self.as_u32()))
}
}rustc_index::newtype_index! {
103/// A [De Bruijn index][dbi] is a standard means of representing
104 /// regions (and perhaps later types) in a higher-ranked setting. In
105 /// particular, imagine a type like this:
106 /// ```ignore (illustrative)
107 /// for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
108 /// // ^ ^ | | |
109 /// // | | | | |
110 /// // | +------------+ 0 | |
111 /// // | | |
112 /// // +----------------------------------+ 1 |
113 /// // | |
114 /// // +----------------------------------------------+ 0
115 /// ```
116 /// In this type, there are two binders (the outer fn and the inner
117 /// fn). We need to be able to determine, for any given region, which
118 /// fn type it is bound by, the inner or the outer one. There are
119 /// various ways you can do this, but a De Bruijn index is one of the
120 /// more convenient and has some nice properties. The basic idea is to
121 /// count the number of binders, inside out. Some examples should help
122 /// clarify what I mean.
123 ///
124 /// Let's start with the reference type `&'b isize` that is the first
125 /// argument to the inner function. This region `'b` is assigned a De
126 /// Bruijn index of 0, meaning "the innermost binder" (in this case, a
127 /// fn). The region `'a` that appears in the second argument type (`&'a
128 /// isize`) would then be assigned a De Bruijn index of 1, meaning "the
129 /// second-innermost binder". (These indices are written on the arrows
130 /// in the diagram).
131 ///
132 /// What is interesting is that De Bruijn index attached to a particular
133 /// variable will vary depending on where it appears. For example,
134 /// the final type `&'a char` also refers to the region `'a` declared on
135 /// the outermost fn. But this time, this reference is not nested within
136 /// any other binders (i.e., it is not an argument to the inner fn, but
137 /// rather the outer one). Therefore, in this case, it is assigned a
138 /// De Bruijn index of 0, because the innermost binder in that location
139 /// is the outer fn.
140 ///
141 /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index
142#[stable_hash]
143 #[encodable]
144 #[orderable]
145 #[debug_format = "DebruijnIndex({})"]
146 #[gate_rustc_only]
147pub struct DebruijnIndex {
148const INNERMOST = 0;
149 }
150}151152impl DebruijnIndex {
153/// Returns the resulting index when this value is moved into
154 /// `amount` number of new binders. So, e.g., if you had
155 ///
156 /// for<'a> fn(&'a x)
157 ///
158 /// and you wanted to change it to
159 ///
160 /// for<'a> fn(for<'b> fn(&'a x))
161 ///
162 /// you would need to shift the index for `'a` into a new binder.
163#[inline]
164 #[must_use]
165pub fn shifted_in(self, amount: u32) -> DebruijnIndex {
166DebruijnIndex::from_u32(self.as_u32() + amount)
167 }
168169/// Update this index in place by shifting it "in" through
170 /// `amount` number of binders.
171#[inline]
172pub fn shift_in(&mut self, amount: u32) {
173*self = self.shifted_in(amount);
174 }
175176/// Returns the resulting index when this value is moved out from
177 /// `amount` number of new binders.
178#[inline]
179 #[must_use]
180pub fn shifted_out(self, amount: u32) -> DebruijnIndex {
181DebruijnIndex::from_u32(self.as_u32() - amount)
182 }
183184/// Update in place by shifting out from `amount` binders.
185#[inline]
186pub fn shift_out(&mut self, amount: u32) {
187*self = self.shifted_out(amount);
188 }
189190/// Adjusts any De Bruijn indices so as to make `to_binder` the
191 /// innermost binder. That is, if we have something bound at `to_binder`,
192 /// it will now be bound at INNERMOST. This is an appropriate thing to do
193 /// when moving a region out from inside binders:
194 ///
195 /// ```ignore (illustrative)
196 /// for<'a> fn(for<'b> for<'c> fn(&'a u32), _)
197 /// // Binder: D3 D2 D1 ^^
198 /// ```
199 ///
200 /// Here, the region `'a` would have the De Bruijn index D3,
201 /// because it is the bound 3 binders out. However, if we wanted
202 /// to refer to that region `'a` in the second argument (the `_`),
203 /// those two binders would not be in scope. In that case, we
204 /// might invoke `shift_out_to_binder(D3)`. This would adjust the
205 /// De Bruijn index of `'a` to D1 (the innermost binder).
206 ///
207 /// If we invoke `shift_out_to_binder` and the region is in fact
208 /// bound by one of the binders we are shifting out of, that is an
209 /// error (and should fail an assertion failure).
210#[inline]
211pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self {
212self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32())
213 }
214}
215216pub fn debug_bound_var<T: std::fmt::Write>(
217 fmt: &mut T,
218 bound_index: BoundVarIndexKind,
219 var: impl std::fmt::Debug,
220) -> Result<(), std::fmt::Error> {
221match bound_index {
222 BoundVarIndexKind::Bound(debruijn) => {
223if debruijn == INNERMOST {
224fmt.write_fmt(format_args!("^{0:?}", var))write!(fmt, "^{var:?}")225 } else {
226fmt.write_fmt(format_args!("^{0}_{1:?}", debruijn.index(), var))write!(fmt, "^{}_{:?}", debruijn.index(), var)227 }
228 }
229 BoundVarIndexKind::Canonical => {
230fmt.write_fmt(format_args!("^c_{0:?}", var))write!(fmt, "^c_{:?}", var)231 }
232 }
233}
234235#[derive(#[automatically_derived]
impl ::core::marker::Copy for Variance { }Copy, #[automatically_derived]
impl ::core::clone::Clone for Variance {
#[inline]
fn clone(&self) -> Variance { *self }
}Clone, #[automatically_derived]
impl ::core::cmp::PartialEq for Variance {
#[inline]
fn eq(&self, other: &Variance) -> bool {
let __self_discr = ::core::intrinsics::discriminant_value(self);
let __arg1_discr = ::core::intrinsics::discriminant_value(other);
__self_discr == __arg1_discr
}
}PartialEq, #[automatically_derived]
impl ::core::cmp::Eq for Variance {
#[inline]
#[doc(hidden)]
#[coverage(off)]
fn assert_fields_are_eq(&self) {}
}Eq, #[automatically_derived]
impl ::core::hash::Hash for Variance {
#[inline]
fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) {
let __self_discr = ::core::intrinsics::discriminant_value(self);
::core::hash::Hash::hash(&__self_discr, state)
}
}Hash, GenericTypeVisitable)]
236#[cfg_attr(feature = "nightly", derive(const _: () =
{
impl<__D: ::rustc_span::SpanDecoder> ::rustc_serialize::Decodable<__D>
for Variance {
fn decode(__decoder: &mut __D) -> Self {
match ::rustc_serialize::Decoder::read_u8(__decoder) as usize
{
0usize => { Variance::Covariant }
1usize => { Variance::Invariant }
2usize => { Variance::Contravariant }
3usize => { Variance::Bivariant }
n => {
::core::panicking::panic_fmt(format_args!("invalid enum variant tag while decoding `Variance`, expected 0..4, actual {0}",
n));
}
}
}
}
};Decodable, const _: () =
{
impl<__E: ::rustc_span::SpanEncoder> ::rustc_serialize::Encodable<__E>
for Variance {
fn encode(&self, __encoder: &mut __E) {
let disc =
match *self {
Variance::Covariant => { 0usize }
Variance::Invariant => { 1usize }
Variance::Contravariant => { 2usize }
Variance::Bivariant => { 3usize }
};
::rustc_serialize::Encoder::emit_u8(__encoder, disc as u8);
match *self {
Variance::Covariant => {}
Variance::Invariant => {}
Variance::Contravariant => {}
Variance::Bivariant => {}
}
}
}
};Encodable, const _: () =
{
impl ::rustc_data_structures::stable_hash::StableHash for Variance {
#[inline]
fn stable_hash<__Hcx: ::rustc_data_structures::stable_hash::StableHashCtxt>(&self,
__hcx: &mut __Hcx,
__hasher:
&mut ::rustc_data_structures::stable_hash::StableHasher) {
::std::mem::discriminant(self).stable_hash(__hcx, __hasher);
match *self {
Variance::Covariant => {}
Variance::Invariant => {}
Variance::Contravariant => {}
Variance::Bivariant => {}
}
}
}
};StableHash))]
237#[cfg_attr(feature = "nightly", rustc_pass_by_value)]
238pub enum Variance {
239 Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type
240Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
241Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
242Bivariant, // T<A> <: T<B> -- e.g., unused type parameter
243}
244245impl Variance {
246/// `a.xform(b)` combines the variance of a context with the
247 /// variance of a type with the following meaning. If we are in a
248 /// context with variance `a`, and we encounter a type argument in
249 /// a position with variance `b`, then `a.xform(b)` is the new
250 /// variance with which the argument appears.
251 ///
252 /// Example 1:
253 /// ```ignore (illustrative)
254 /// *mut Vec<i32>
255 /// ```
256 /// Here, the "ambient" variance starts as covariant. `*mut T` is
257 /// invariant with respect to `T`, so the variance in which the
258 /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which
259 /// yields `Invariant`. Now, the type `Vec<T>` is covariant with
260 /// respect to its type argument `T`, and hence the variance of
261 /// the `i32` here is `Invariant.xform(Covariant)`, which results
262 /// (again) in `Invariant`.
263 ///
264 /// Example 2:
265 /// ```ignore (illustrative)
266 /// fn(*const Vec<i32>, *mut Vec<i32)
267 /// ```
268 /// The ambient variance is covariant. A `fn` type is
269 /// contravariant with respect to its parameters, so the variance
270 /// within which both pointer types appear is
271 /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const
272 /// T` is covariant with respect to `T`, so the variance within
273 /// which the first `Vec<i32>` appears is
274 /// `Contravariant.xform(Covariant)` or `Contravariant`. The same
275 /// is true for its `i32` argument. In the `*mut T` case, the
276 /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`,
277 /// and hence the outermost type is `Invariant` with respect to
278 /// `Vec<i32>` (and its `i32` argument).
279 ///
280 /// Source: Figure 1 of "Taming the Wildcards:
281 /// Combining Definition- and Use-Site Variance" published in PLDI'11.
282pub fn xform(self, v: Variance) -> Variance {
283match (self, v) {
284// Figure 1, column 1.
285(Variance::Covariant, Variance::Covariant) => Variance::Covariant,
286 (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant,
287 (Variance::Covariant, Variance::Invariant) => Variance::Invariant,
288 (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant,
289290// Figure 1, column 2.
291(Variance::Contravariant, Variance::Covariant) => Variance::Contravariant,
292 (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
293 (Variance::Contravariant, Variance::Invariant) => Variance::Invariant,
294 (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant,
295296// Figure 1, column 3.
297(Variance::Invariant, _) => Variance::Invariant,
298299// Figure 1, column 4.
300(Variance::Bivariant, _) => Variance::Bivariant,
301 }
302 }
303}
304305impl fmt::Debugfor Variance {
306fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307f.write_str(match *self {
308 Variance::Covariant => "+",
309 Variance::Contravariant => "-",
310 Variance::Invariant => "o",
311 Variance::Bivariant => "*",
312 })
313 }
314}
315316impl ::std::fmt::Debug for UniverseIndex {
fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
fmt.write_fmt(format_args!("U{0}", self.as_u32()))
}
}rustc_index::newtype_index! {
317/// "Universes" are used during type- and trait-checking in the
318 /// presence of `for<..>` binders to control what sets of names are
319 /// visible. Universes are arranged into a tree: the root universe
320 /// contains names that are always visible. Each child then adds a new
321 /// set of names that are visible, in addition to those of its parent.
322 /// We say that the child universe "extends" the parent universe with
323 /// new names.
324 ///
325 /// To make this more concrete, consider this program:
326 ///
327 /// ```ignore (illustrative)
328 /// struct Foo { }
329 /// fn bar<T>(x: T) {
330 /// let y: for<'a> fn(&'a u8, Foo) = ...;
331 /// }
332 /// ```
333 ///
334 /// The struct name `Foo` is in the root universe U0. But the type
335 /// parameter `T`, introduced on `bar`, is in an extended universe U1
336 /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
337 /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
338 /// region `'a` is in a universe U2 that extends U1, because we can
339 /// name it inside the fn type but not outside.
340 ///
341 /// Universes are used to do type- and trait-checking around these
342 /// "forall" binders (also called **universal quantification**). The
343 /// idea is that when, in the body of `bar`, we refer to `T` as a
344 /// type, we aren't referring to any type in particular, but rather a
345 /// kind of "fresh" type that is distinct from all other types we have
346 /// actually declared. This is called a **placeholder** type, and we
347 /// use universes to talk about this. In other words, a type name in
348 /// universe 0 always corresponds to some "ground" type that the user
349 /// declared, but a type name in a non-zero universe is a placeholder
350 /// type -- an idealized representative of "types in general" that we
351 /// use for checking generic functions.
352#[stable_hash]
353 #[encodable]
354 #[orderable]
355 #[debug_format = "U{}"]
356 #[gate_rustc_only]
357pub struct UniverseIndex {}
358}359360impl UniverseIndex {
361pub const ROOT: UniverseIndex = UniverseIndex::ZERO;
362363/// Returns the "next" universe index in order -- this new index
364 /// is considered to extend all previous universes. This
365 /// corresponds to entering a `forall` quantifier. So, for
366 /// example, suppose we have this type in universe `U`:
367 ///
368 /// ```ignore (illustrative)
369 /// for<'a> fn(&'a u32)
370 /// ```
371 ///
372 /// Once we "enter" into this `for<'a>` quantifier, we are in a
373 /// new universe that extends `U` -- in this new universe, we can
374 /// name the region `'a`, but that region was not nameable from
375 /// `U` because it was not in scope there.
376pub fn next_universe(self) -> UniverseIndex {
377UniverseIndex::from_u32(self.as_u32().checked_add(1).unwrap())
378 }
379380/// Returns `true` if `self` can name a name from `other` -- in other words,
381 /// if the set of names in `self` is a superset of those in
382 /// `other` (`self >= other`).
383pub fn can_name(self, other: UniverseIndex) -> bool {
384self >= other385 }
386387/// Returns `true` if `self` cannot name some names from `other` -- in other
388 /// words, if the set of names in `self` is a strict subset of
389 /// those in `other` (`self < other`).
390pub fn cannot_name(self, other: UniverseIndex) -> bool {
391self < other392 }
393394/// Returns `true` if `self` is the root universe, otherwise false.
395pub fn is_root(self) -> bool {
396self == Self::ROOT397 }
398}
399400impl Defaultfor UniverseIndex {
401fn default() -> Self {
402Self::ROOT403 }
404}
405406impl ::std::fmt::Debug for BoundVar {
fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
fmt.write_fmt(format_args!("{0}", self.as_u32()))
}
}rustc_index::newtype_index! {
407#[stable_hash]
408 #[encodable]
409 #[orderable]
410 #[debug_format = "{}"]
411 #[gate_rustc_only]
412pub struct BoundVar {}
413}414415/// Represents the various closure traits in the language. This
416/// will determine the type of the environment (`self`, in the
417/// desugaring) argument that the closure expects.
418///
419/// You can get the environment type of a closure using
420/// `tcx.closure_env_ty()`.
421#[derive(#[automatically_derived]
impl ::core::clone::Clone for ClosureKind {
#[inline]
fn clone(&self) -> ClosureKind { *self }
}Clone, #[automatically_derived]
impl ::core::marker::Copy for ClosureKind { }Copy, #[automatically_derived]
impl ::core::cmp::PartialEq for ClosureKind {
#[inline]
fn eq(&self, other: &ClosureKind) -> bool {
let __self_discr = ::core::intrinsics::discriminant_value(self);
let __arg1_discr = ::core::intrinsics::discriminant_value(other);
__self_discr == __arg1_discr
}
}PartialEq, #[automatically_derived]
impl ::core::cmp::Eq for ClosureKind {
#[inline]
#[doc(hidden)]
#[coverage(off)]
fn assert_fields_are_eq(&self) {}
}Eq, #[automatically_derived]
impl ::core::hash::Hash for ClosureKind {
#[inline]
fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) {
let __self_discr = ::core::intrinsics::discriminant_value(self);
::core::hash::Hash::hash(&__self_discr, state)
}
}Hash, #[automatically_derived]
impl ::core::fmt::Debug for ClosureKind {
#[inline]
fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
::core::fmt::Formatter::write_str(f,
match self {
ClosureKind::Fn => "Fn",
ClosureKind::FnMut => "FnMut",
ClosureKind::FnOnce => "FnOnce",
})
}
}Debug)]
422#[cfg_attr(feature = "nightly", derive(const _: () =
{
impl<__E: ::rustc_span::SpanEncoder> ::rustc_serialize::Encodable<__E>
for ClosureKind {
fn encode(&self, __encoder: &mut __E) {
let disc =
match *self {
ClosureKind::Fn => { 0usize }
ClosureKind::FnMut => { 1usize }
ClosureKind::FnOnce => { 2usize }
};
::rustc_serialize::Encoder::emit_u8(__encoder, disc as u8);
match *self {
ClosureKind::Fn => {}
ClosureKind::FnMut => {}
ClosureKind::FnOnce => {}
}
}
}
};Encodable, const _: () =
{
impl<__D: ::rustc_span::SpanDecoder> ::rustc_serialize::Decodable<__D>
for ClosureKind {
fn decode(__decoder: &mut __D) -> Self {
match ::rustc_serialize::Decoder::read_u8(__decoder) as usize
{
0usize => { ClosureKind::Fn }
1usize => { ClosureKind::FnMut }
2usize => { ClosureKind::FnOnce }
n => {
::core::panicking::panic_fmt(format_args!("invalid enum variant tag while decoding `ClosureKind`, expected 0..3, actual {0}",
n));
}
}
}
}
};Decodable, const _: () =
{
impl ::rustc_data_structures::stable_hash::StableHash for ClosureKind
{
#[inline]
fn stable_hash<__Hcx: ::rustc_data_structures::stable_hash::StableHashCtxt>(&self,
__hcx: &mut __Hcx,
__hasher:
&mut ::rustc_data_structures::stable_hash::StableHasher) {
::std::mem::discriminant(self).stable_hash(__hcx, __hasher);
match *self {
ClosureKind::Fn => {}
ClosureKind::FnMut => {}
ClosureKind::FnOnce => {}
}
}
}
};StableHash))]
423pub enum ClosureKind {
424 Fn,
425 FnMut,
426 FnOnce,
427}
428429impl ClosureKind {
430/// This is the initial value used when doing upvar inference.
431pub const LATTICE_BOTTOM: ClosureKind = ClosureKind::Fn;
432433pub const fn as_str(self) -> &'static str {
434match self {
435 ClosureKind::Fn => "Fn",
436 ClosureKind::FnMut => "FnMut",
437 ClosureKind::FnOnce => "FnOnce",
438 }
439 }
440441/// Returns `true` if a type that impls this closure kind
442 /// must also implement `other`.
443#[rustfmt::skip]
444pub fn extends(self, other: ClosureKind) -> bool {
445use ClosureKind::*;
446match (self, other) {
447 (Fn, Fn | FnMut | FnOnce)
448 | (FnMut, FnMut | FnOnce)
449 | (FnOnce, FnOnce) => true,
450_ => false,
451 }
452 }
453}
454455impl fmt::Displayfor ClosureKind {
456fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
457self.as_str().fmt(f)
458 }
459}
460461pub struct FieldInfo<I: Interner> {
462pub base: I::Ty,
463pub ty: I::Ty,
464pub variant: Option<I::Symbol>,
465pub variant_idx: VariantIdx,
466pub name: I::Symbol,
467pub field_idx: FieldIdx,
468}