rustc_type_ir/
lib.rs

1// tidy-alphabetical-start
2#![allow(rustc::usage_of_ty_tykind)]
3#![allow(rustc::usage_of_type_ir_inherent)]
4#![allow(rustc::usage_of_type_ir_traits)]
5#![cfg_attr(
6    feature = "nightly",
7    feature(associated_type_defaults, never_type, rustc_attrs, negative_impls)
8)]
9#![cfg_attr(feature = "nightly", allow(internal_features))]
10// tidy-alphabetical-end
11
12extern crate self as rustc_type_ir;
13
14use std::fmt;
15use std::hash::Hash;
16
17#[cfg(feature = "nightly")]
18use rustc_macros::{Decodable, Encodable, HashStable_NoContext};
19
20// 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 ir_print;
28pub mod lang_items;
29pub mod lift;
30pub mod outlives;
31pub mod relate;
32pub mod search_graph;
33pub mod solve;
34pub mod walk;
35
36// These modules are not `pub` since they are glob-imported.
37#[macro_use]
38mod macros;
39mod binder;
40mod canonical;
41mod const_kind;
42mod flags;
43mod fold;
44mod generic_arg;
45mod infer_ctxt;
46mod interner;
47mod opaque_ty;
48mod pattern;
49mod predicate;
50mod predicate_kind;
51mod region_kind;
52mod ty_info;
53mod ty_kind;
54mod upcast;
55mod visit;
56
57pub use AliasTyKind::*;
58pub use DynKind::*;
59pub use InferTy::*;
60pub use RegionKind::*;
61pub use TyKind::*;
62pub use Variance::*;
63pub use binder::*;
64pub use canonical::*;
65pub use const_kind::*;
66pub use flags::*;
67pub use fold::*;
68pub use generic_arg::*;
69pub use infer_ctxt::*;
70pub use interner::*;
71pub use opaque_ty::*;
72pub use pattern::*;
73pub use predicate::*;
74pub use predicate_kind::*;
75pub use region_kind::*;
76pub use rustc_ast_ir::{Movability, Mutability, Pinnedness};
77pub use ty_info::*;
78pub use ty_kind::*;
79pub use upcast::*;
80pub use visit::*;
81
82rustc_index::newtype_index! {
83    /// A [De Bruijn index][dbi] is a standard means of representing
84    /// regions (and perhaps later types) in a higher-ranked setting. In
85    /// particular, imagine a type like this:
86    /// ```ignore (illustrative)
87    ///    for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
88    /// // ^          ^            |          |           |
89    /// // |          |            |          |           |
90    /// // |          +------------+ 0        |           |
91    /// // |                                  |           |
92    /// // +----------------------------------+ 1         |
93    /// // |                                              |
94    /// // +----------------------------------------------+ 0
95    /// ```
96    /// In this type, there are two binders (the outer fn and the inner
97    /// fn). We need to be able to determine, for any given region, which
98    /// fn type it is bound by, the inner or the outer one. There are
99    /// various ways you can do this, but a De Bruijn index is one of the
100    /// more convenient and has some nice properties. The basic idea is to
101    /// count the number of binders, inside out. Some examples should help
102    /// clarify what I mean.
103    ///
104    /// Let's start with the reference type `&'b isize` that is the first
105    /// argument to the inner function. This region `'b` is assigned a De
106    /// Bruijn index of 0, meaning "the innermost binder" (in this case, a
107    /// fn). The region `'a` that appears in the second argument type (`&'a
108    /// isize`) would then be assigned a De Bruijn index of 1, meaning "the
109    /// second-innermost binder". (These indices are written on the arrows
110    /// in the diagram).
111    ///
112    /// What is interesting is that De Bruijn index attached to a particular
113    /// variable will vary depending on where it appears. For example,
114    /// the final type `&'a char` also refers to the region `'a` declared on
115    /// the outermost fn. But this time, this reference is not nested within
116    /// any other binders (i.e., it is not an argument to the inner fn, but
117    /// rather the outer one). Therefore, in this case, it is assigned a
118    /// De Bruijn index of 0, because the innermost binder in that location
119    /// is the outer fn.
120    ///
121    /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index
122    #[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
123    #[encodable]
124    #[orderable]
125    #[debug_format = "DebruijnIndex({})"]
126    #[gate_rustc_only]
127    pub struct DebruijnIndex {
128        const INNERMOST = 0;
129    }
130}
131
132impl DebruijnIndex {
133    /// Returns the resulting index when this value is moved into
134    /// `amount` number of new binders. So, e.g., if you had
135    ///
136    ///    for<'a> fn(&'a x)
137    ///
138    /// and you wanted to change it to
139    ///
140    ///    for<'a> fn(for<'b> fn(&'a x))
141    ///
142    /// you would need to shift the index for `'a` into a new binder.
143    #[inline]
144    #[must_use]
145    pub fn shifted_in(self, amount: u32) -> DebruijnIndex {
146        DebruijnIndex::from_u32(self.as_u32() + amount)
147    }
148
149    /// Update this index in place by shifting it "in" through
150    /// `amount` number of binders.
151    #[inline]
152    pub fn shift_in(&mut self, amount: u32) {
153        *self = self.shifted_in(amount);
154    }
155
156    /// Returns the resulting index when this value is moved out from
157    /// `amount` number of new binders.
158    #[inline]
159    #[must_use]
160    pub fn shifted_out(self, amount: u32) -> DebruijnIndex {
161        DebruijnIndex::from_u32(self.as_u32() - amount)
162    }
163
164    /// Update in place by shifting out from `amount` binders.
165    #[inline]
166    pub fn shift_out(&mut self, amount: u32) {
167        *self = self.shifted_out(amount);
168    }
169
170    /// Adjusts any De Bruijn indices so as to make `to_binder` the
171    /// innermost binder. That is, if we have something bound at `to_binder`,
172    /// it will now be bound at INNERMOST. This is an appropriate thing to do
173    /// when moving a region out from inside binders:
174    ///
175    /// ```ignore (illustrative)
176    ///             for<'a>   fn(for<'b>   for<'c>   fn(&'a u32), _)
177    /// // Binder:  D3           D2        D1            ^^
178    /// ```
179    ///
180    /// Here, the region `'a` would have the De Bruijn index D3,
181    /// because it is the bound 3 binders out. However, if we wanted
182    /// to refer to that region `'a` in the second argument (the `_`),
183    /// those two binders would not be in scope. In that case, we
184    /// might invoke `shift_out_to_binder(D3)`. This would adjust the
185    /// De Bruijn index of `'a` to D1 (the innermost binder).
186    ///
187    /// If we invoke `shift_out_to_binder` and the region is in fact
188    /// bound by one of the binders we are shifting out of, that is an
189    /// error (and should fail an assertion failure).
190    #[inline]
191    pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self {
192        self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32())
193    }
194}
195
196pub fn debug_bound_var<T: std::fmt::Write>(
197    fmt: &mut T,
198    debruijn: DebruijnIndex,
199    var: impl std::fmt::Debug,
200) -> Result<(), std::fmt::Error> {
201    if debruijn == INNERMOST {
202        write!(fmt, "^{var:?}")
203    } else {
204        write!(fmt, "^{}_{:?}", debruijn.index(), var)
205    }
206}
207
208#[derive(Copy, Clone, PartialEq, Eq, Hash)]
209#[cfg_attr(feature = "nightly", derive(Decodable, Encodable, HashStable_NoContext))]
210#[cfg_attr(feature = "nightly", rustc_pass_by_value)]
211pub enum Variance {
212    Covariant,     // T<A> <: T<B> iff A <: B -- e.g., function return type
213    Invariant,     // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
214    Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
215    Bivariant,     // T<A> <: T<B>            -- e.g., unused type parameter
216}
217
218impl Variance {
219    /// `a.xform(b)` combines the variance of a context with the
220    /// variance of a type with the following meaning. If we are in a
221    /// context with variance `a`, and we encounter a type argument in
222    /// a position with variance `b`, then `a.xform(b)` is the new
223    /// variance with which the argument appears.
224    ///
225    /// Example 1:
226    /// ```ignore (illustrative)
227    /// *mut Vec<i32>
228    /// ```
229    /// Here, the "ambient" variance starts as covariant. `*mut T` is
230    /// invariant with respect to `T`, so the variance in which the
231    /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which
232    /// yields `Invariant`. Now, the type `Vec<T>` is covariant with
233    /// respect to its type argument `T`, and hence the variance of
234    /// the `i32` here is `Invariant.xform(Covariant)`, which results
235    /// (again) in `Invariant`.
236    ///
237    /// Example 2:
238    /// ```ignore (illustrative)
239    /// fn(*const Vec<i32>, *mut Vec<i32)
240    /// ```
241    /// The ambient variance is covariant. A `fn` type is
242    /// contravariant with respect to its parameters, so the variance
243    /// within which both pointer types appear is
244    /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const
245    /// T` is covariant with respect to `T`, so the variance within
246    /// which the first `Vec<i32>` appears is
247    /// `Contravariant.xform(Covariant)` or `Contravariant`. The same
248    /// is true for its `i32` argument. In the `*mut T` case, the
249    /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`,
250    /// and hence the outermost type is `Invariant` with respect to
251    /// `Vec<i32>` (and its `i32` argument).
252    ///
253    /// Source: Figure 1 of "Taming the Wildcards:
254    /// Combining Definition- and Use-Site Variance" published in PLDI'11.
255    pub fn xform(self, v: Variance) -> Variance {
256        match (self, v) {
257            // Figure 1, column 1.
258            (Variance::Covariant, Variance::Covariant) => Variance::Covariant,
259            (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant,
260            (Variance::Covariant, Variance::Invariant) => Variance::Invariant,
261            (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant,
262
263            // Figure 1, column 2.
264            (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant,
265            (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
266            (Variance::Contravariant, Variance::Invariant) => Variance::Invariant,
267            (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant,
268
269            // Figure 1, column 3.
270            (Variance::Invariant, _) => Variance::Invariant,
271
272            // Figure 1, column 4.
273            (Variance::Bivariant, _) => Variance::Bivariant,
274        }
275    }
276}
277
278impl fmt::Debug for Variance {
279    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
280        f.write_str(match *self {
281            Variance::Covariant => "+",
282            Variance::Contravariant => "-",
283            Variance::Invariant => "o",
284            Variance::Bivariant => "*",
285        })
286    }
287}
288
289rustc_index::newtype_index! {
290    /// "Universes" are used during type- and trait-checking in the
291    /// presence of `for<..>` binders to control what sets of names are
292    /// visible. Universes are arranged into a tree: the root universe
293    /// contains names that are always visible. Each child then adds a new
294    /// set of names that are visible, in addition to those of its parent.
295    /// We say that the child universe "extends" the parent universe with
296    /// new names.
297    ///
298    /// To make this more concrete, consider this program:
299    ///
300    /// ```ignore (illustrative)
301    /// struct Foo { }
302    /// fn bar<T>(x: T) {
303    ///   let y: for<'a> fn(&'a u8, Foo) = ...;
304    /// }
305    /// ```
306    ///
307    /// The struct name `Foo` is in the root universe U0. But the type
308    /// parameter `T`, introduced on `bar`, is in an extended universe U1
309    /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
310    /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
311    /// region `'a` is in a universe U2 that extends U1, because we can
312    /// name it inside the fn type but not outside.
313    ///
314    /// Universes are used to do type- and trait-checking around these
315    /// "forall" binders (also called **universal quantification**). The
316    /// idea is that when, in the body of `bar`, we refer to `T` as a
317    /// type, we aren't referring to any type in particular, but rather a
318    /// kind of "fresh" type that is distinct from all other types we have
319    /// actually declared. This is called a **placeholder** type, and we
320    /// use universes to talk about this. In other words, a type name in
321    /// universe 0 always corresponds to some "ground" type that the user
322    /// declared, but a type name in a non-zero universe is a placeholder
323    /// type -- an idealized representative of "types in general" that we
324    /// use for checking generic functions.
325    #[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
326    #[encodable]
327    #[orderable]
328    #[debug_format = "U{}"]
329    #[gate_rustc_only]
330    pub struct UniverseIndex {}
331}
332
333impl UniverseIndex {
334    pub const ROOT: UniverseIndex = UniverseIndex::ZERO;
335
336    /// Returns the "next" universe index in order -- this new index
337    /// is considered to extend all previous universes. This
338    /// corresponds to entering a `forall` quantifier. So, for
339    /// example, suppose we have this type in universe `U`:
340    ///
341    /// ```ignore (illustrative)
342    /// for<'a> fn(&'a u32)
343    /// ```
344    ///
345    /// Once we "enter" into this `for<'a>` quantifier, we are in a
346    /// new universe that extends `U` -- in this new universe, we can
347    /// name the region `'a`, but that region was not nameable from
348    /// `U` because it was not in scope there.
349    pub fn next_universe(self) -> UniverseIndex {
350        UniverseIndex::from_u32(self.as_u32().checked_add(1).unwrap())
351    }
352
353    /// Returns `true` if `self` can name a name from `other` -- in other words,
354    /// if the set of names in `self` is a superset of those in
355    /// `other` (`self >= other`).
356    pub fn can_name(self, other: UniverseIndex) -> bool {
357        self >= other
358    }
359
360    /// Returns `true` if `self` cannot name some names from `other` -- in other
361    /// words, if the set of names in `self` is a strict subset of
362    /// those in `other` (`self < other`).
363    pub fn cannot_name(self, other: UniverseIndex) -> bool {
364        self < other
365    }
366
367    /// Returns `true` if `self` is the root universe, otherwise false.
368    pub fn is_root(self) -> bool {
369        self == Self::ROOT
370    }
371}
372
373impl Default for UniverseIndex {
374    fn default() -> Self {
375        Self::ROOT
376    }
377}
378
379rustc_index::newtype_index! {
380    #[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
381    #[encodable]
382    #[orderable]
383    #[debug_format = "{}"]
384    #[gate_rustc_only]
385    pub struct BoundVar {}
386}
387
388impl<I: Interner> inherent::BoundVarLike<I> for BoundVar {
389    fn var(self) -> BoundVar {
390        self
391    }
392
393    fn assert_eq(self, _var: I::BoundVarKind) {
394        unreachable!("FIXME: We really should have a separate `BoundConst` for consts")
395    }
396}
397
398/// Represents the various closure traits in the language. This
399/// will determine the type of the environment (`self`, in the
400/// desugaring) argument that the closure expects.
401///
402/// You can get the environment type of a closure using
403/// `tcx.closure_env_ty()`.
404#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
405#[cfg_attr(feature = "nightly", derive(Encodable, Decodable, HashStable_NoContext))]
406pub enum ClosureKind {
407    Fn,
408    FnMut,
409    FnOnce,
410}
411
412impl ClosureKind {
413    /// This is the initial value used when doing upvar inference.
414    pub const LATTICE_BOTTOM: ClosureKind = ClosureKind::Fn;
415
416    pub const fn as_str(self) -> &'static str {
417        match self {
418            ClosureKind::Fn => "Fn",
419            ClosureKind::FnMut => "FnMut",
420            ClosureKind::FnOnce => "FnOnce",
421        }
422    }
423
424    /// Returns `true` if a type that impls this closure kind
425    /// must also implement `other`.
426    #[rustfmt::skip]
427    pub fn extends(self, other: ClosureKind) -> bool {
428        use ClosureKind::*;
429        match (self, other) {
430              (Fn, Fn | FnMut | FnOnce)
431            | (FnMut,   FnMut | FnOnce)
432            | (FnOnce,          FnOnce) => true,
433            _ => false,
434        }
435    }
436}
437
438impl fmt::Display for ClosureKind {
439    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
440        self.as_str().fmt(f)
441    }
442}
rustc_type_ir/lib.rs

rustc_type_ir/
lib.rs
