rustc_type_ir/
lib.rs

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

rustc_type_ir/
lib.rs
