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

rustc_type_ir/
lib.rs
