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

rustc_type_ir/
lib.rs
