rustc_type_ir/
lib.rs

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

rustc_type_ir/
lib.rs
