rustc_type_ir/
canonical.rs

Help
1use std::fmt;
2use std::hash::Hash;
3use std::ops::Index;
4
5use derive_where::derive_where;
6#[cfg(feature = "nightly")]
7use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
8use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic};
9
10use crate::inherent::*;
11use crate::{self as ty, Interner, TypingMode, UniverseIndex};
12
13#[derive_where(Clone; I: Interner, V: Clone)]
14#[derive_where(Hash; I: Interner, V: Hash)]
15#[derive_where(PartialEq; I: Interner, V: PartialEq)]
16#[derive_where(Eq; I: Interner, V: Eq)]
17#[derive_where(Debug; I: Interner, V: fmt::Debug)]
18#[derive_where(Copy; I: Interner, V: Copy)]
19#[cfg_attr(
20    feature = "nightly",
21    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
22)]
23pub struct CanonicalQueryInput<I: Interner, V> {
24    pub canonical: Canonical<I, V>,
25    pub typing_mode: TypingMode<I>,
26}
27
28/// A "canonicalized" type `V` is one where all free inference
29/// variables have been rewritten to "canonical vars". These are
30/// numbered starting from 0 in order of first appearance.
31#[derive_where(Clone; I: Interner, V: Clone)]
32#[derive_where(Hash; I: Interner, V: Hash)]
33#[derive_where(PartialEq; I: Interner, V: PartialEq)]
34#[derive_where(Eq; I: Interner, V: Eq)]
35#[derive_where(Debug; I: Interner, V: fmt::Debug)]
36#[derive_where(Copy; I: Interner, V: Copy)]
37#[cfg_attr(
38    feature = "nightly",
39    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
40)]
41pub struct Canonical<I: Interner, V> {
42    pub value: V,
43    pub max_universe: UniverseIndex,
44    pub variables: I::CanonicalVarKinds,
45}
46
47impl<I: Interner, V> Canonical<I, V> {
48    /// Allows you to map the `value` of a canonical while keeping the
49    /// same set of bound variables.
50    ///
51    /// **WARNING:** This function is very easy to mis-use, hence the
52    /// name!  In particular, the new value `W` must use all **the
53    /// same type/region variables** in **precisely the same order**
54    /// as the original! (The ordering is defined by the
55    /// `TypeFoldable` implementation of the type in question.)
56    ///
57    /// An example of a **correct** use of this:
58    ///
59    /// ```rust,ignore (not real code)
60    /// let a: Canonical<I, T> = ...;
61    /// let b: Canonical<I, (T,)> = a.unchecked_map(|v| (v, ));
62    /// ```
63    ///
64    /// An example of an **incorrect** use of this:
65    ///
66    /// ```rust,ignore (not real code)
67    /// let a: Canonical<I, T> = ...;
68    /// let ty: Ty<I> = ...;
69    /// let b: Canonical<I, (T, Ty<I>)> = a.unchecked_map(|v| (v, ty));
70    /// ```
71    pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<I, W> {
72        let Canonical { max_universe, variables, value } = self;
73        Canonical { max_universe, variables, value: map_op(value) }
74    }
75}
76
77impl<I: Interner, V: fmt::Display> fmt::Display for Canonical<I, V> {
78    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
79        let Self { value, max_universe, variables } = self;
80        write!(
81            f,
82            "Canonical {{ value: {value}, max_universe: {max_universe:?}, variables: {variables:?} }}",
83        )
84    }
85}
86
87/// Information about a canonical variable that is included with the
88/// canonical value. This is sufficient information for code to create
89/// a copy of the canonical value in some other inference context,
90/// with fresh inference variables replacing the canonical values.
91#[derive_where(Clone, Copy, Hash, PartialEq, Eq, Debug; I: Interner)]
92#[cfg_attr(
93    feature = "nightly",
94    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
95)]
96pub enum CanonicalVarKind<I: Interner> {
97    /// Some kind of type inference variable.
98    Ty(CanonicalTyVarKind),
99
100    /// A "placeholder" that represents "any type".
101    PlaceholderTy(I::PlaceholderTy),
102
103    /// Region variable `'?R`.
104    Region(UniverseIndex),
105
106    /// A "placeholder" that represents "any region". Created when you
107    /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
108    /// bound region `'a`.
109    PlaceholderRegion(I::PlaceholderRegion),
110
111    /// Some kind of const inference variable.
112    Const(UniverseIndex),
113
114    /// A "placeholder" that represents "any const".
115    PlaceholderConst(I::PlaceholderConst),
116}
117
118impl<I: Interner> CanonicalVarKind<I> {
119    pub fn universe(self) -> UniverseIndex {
120        match self {
121            CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)) => ui,
122            CanonicalVarKind::Region(ui) => ui,
123            CanonicalVarKind::Const(ui) => ui,
124            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe(),
125            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe(),
126            CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe(),
127            CanonicalVarKind::Ty(CanonicalTyVarKind::Float | CanonicalTyVarKind::Int) => {
128                UniverseIndex::ROOT
129            }
130        }
131    }
132
133    /// Replaces the universe of this canonical variable with `ui`.
134    ///
135    /// In case this is a float or int variable, this causes an ICE if
136    /// the updated universe is not the root.
137    pub fn with_updated_universe(self, ui: UniverseIndex) -> CanonicalVarKind<I> {
138        match self {
139            CanonicalVarKind::Ty(CanonicalTyVarKind::General(_)) => {
140                CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui))
141            }
142            CanonicalVarKind::Region(_) => CanonicalVarKind::Region(ui),
143            CanonicalVarKind::Const(_) => CanonicalVarKind::Const(ui),
144
145            CanonicalVarKind::PlaceholderTy(placeholder) => {
146                CanonicalVarKind::PlaceholderTy(placeholder.with_updated_universe(ui))
147            }
148            CanonicalVarKind::PlaceholderRegion(placeholder) => {
149                CanonicalVarKind::PlaceholderRegion(placeholder.with_updated_universe(ui))
150            }
151            CanonicalVarKind::PlaceholderConst(placeholder) => {
152                CanonicalVarKind::PlaceholderConst(placeholder.with_updated_universe(ui))
153            }
154            CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => {
155                assert_eq!(ui, UniverseIndex::ROOT);
156                self
157            }
158        }
159    }
160
161    pub fn is_existential(self) -> bool {
162        match self {
163            CanonicalVarKind::Ty(_) => true,
164            CanonicalVarKind::PlaceholderTy(_) => false,
165            CanonicalVarKind::Region(_) => true,
166            CanonicalVarKind::PlaceholderRegion(..) => false,
167            CanonicalVarKind::Const(_) => true,
168            CanonicalVarKind::PlaceholderConst(_) => false,
169        }
170    }
171
172    pub fn is_region(self) -> bool {
173        match self {
174            CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => true,
175            CanonicalVarKind::Ty(_)
176            | CanonicalVarKind::PlaceholderTy(_)
177            | CanonicalVarKind::Const(_)
178            | CanonicalVarKind::PlaceholderConst(_) => false,
179        }
180    }
181
182    pub fn expect_placeholder_index(self) -> usize {
183        match self {
184            CanonicalVarKind::Ty(_) | CanonicalVarKind::Region(_) | CanonicalVarKind::Const(_) => {
185                panic!("expected placeholder: {self:?}")
186            }
187
188            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.var().as_usize(),
189            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.var().as_usize(),
190            CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.var().as_usize(),
191        }
192    }
193}
194
195/// Rust actually has more than one category of type variables;
196/// notably, the type variables we create for literals (e.g., 22 or
197/// 22.) can only be instantiated with integral/float types (e.g.,
198/// usize or f32). In order to faithfully reproduce a type, we need to
199/// know what set of types a given type variable can be unified with.
200#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
201#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
202#[cfg_attr(
203    feature = "nightly",
204    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
205)]
206pub enum CanonicalTyVarKind {
207    /// General type variable `?T` that can be unified with arbitrary types.
208    General(UniverseIndex),
209
210    /// Integral type variable `?I` (that can only be unified with integral types).
211    Int,
212
213    /// Floating-point type variable `?F` (that can only be unified with float types).
214    Float,
215}
216
217/// A set of values corresponding to the canonical variables from some
218/// `Canonical`. You can give these values to
219/// `canonical_value.instantiate` to instantiate them into the canonical
220/// value at the right places.
221///
222/// When you canonicalize a value `V`, you get back one of these
223/// vectors with the original values that were replaced by canonical
224/// variables. You will need to supply it later to instantiate the
225/// canonicalized query response.
226#[derive_where(Clone, Copy, Hash, PartialEq, Eq, Debug; I: Interner)]
227#[cfg_attr(
228    feature = "nightly",
229    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
230)]
231#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
232pub struct CanonicalVarValues<I: Interner> {
233    pub var_values: I::GenericArgs,
234}
235
236impl<I: Interner> CanonicalVarValues<I> {
237    pub fn is_identity(&self) -> bool {
238        self.var_values.iter().enumerate().all(|(bv, arg)| match arg.kind() {
239            ty::GenericArgKind::Lifetime(r) => {
240                matches!(r.kind(), ty::ReBound(ty::INNERMOST, br) if br.var().as_usize() == bv)
241            }
242            ty::GenericArgKind::Type(ty) => {
243                matches!(ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var().as_usize() == bv)
244            }
245            ty::GenericArgKind::Const(ct) => {
246                matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc.var().as_usize() == bv)
247            }
248        })
249    }
250
251    pub fn is_identity_modulo_regions(&self) -> bool {
252        let mut var = ty::BoundVar::ZERO;
253        for arg in self.var_values.iter() {
254            match arg.kind() {
255                ty::GenericArgKind::Lifetime(r) => {
256                    if matches!(r.kind(), ty::ReBound(ty::INNERMOST, br) if var == br.var()) {
257                        var = var + 1;
258                    } else {
259                        // It's ok if this region var isn't an identity variable
260                    }
261                }
262                ty::GenericArgKind::Type(ty) => {
263                    if matches!(ty.kind(), ty::Bound(ty::INNERMOST, bt) if var == bt.var()) {
264                        var = var + 1;
265                    } else {
266                        return false;
267                    }
268                }
269                ty::GenericArgKind::Const(ct) => {
270                    if matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if var == bc.var())
271                    {
272                        var = var + 1;
273                    } else {
274                        return false;
275                    }
276                }
277            }
278        }
279
280        true
281    }
282
283    // Given a list of canonical variables, construct a set of values which are
284    // the identity response.
285    pub fn make_identity(cx: I, infos: I::CanonicalVarKinds) -> CanonicalVarValues<I> {
286        CanonicalVarValues {
287            var_values: cx.mk_args_from_iter(infos.iter().enumerate().map(
288                |(i, kind)| -> I::GenericArg {
289                    match kind {
290                        CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
291                            Ty::new_anon_bound(cx, ty::INNERMOST, ty::BoundVar::from_usize(i))
292                                .into()
293                        }
294                        CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
295                            Region::new_anon_bound(cx, ty::INNERMOST, ty::BoundVar::from_usize(i))
296                                .into()
297                        }
298                        CanonicalVarKind::Const(_) | CanonicalVarKind::PlaceholderConst(_) => {
299                            Const::new_anon_bound(cx, ty::INNERMOST, ty::BoundVar::from_usize(i))
300                                .into()
301                        }
302                    }
303                },
304            )),
305        }
306    }
307
308    /// Creates dummy var values which should not be used in a
309    /// canonical response.
310    pub fn dummy() -> CanonicalVarValues<I> {
311        CanonicalVarValues { var_values: Default::default() }
312    }
313
314    #[inline]
315    pub fn len(&self) -> usize {
316        self.var_values.len()
317    }
318}
319
320impl<'a, I: Interner> IntoIterator for &'a CanonicalVarValues<I> {
321    type Item = I::GenericArg;
322    type IntoIter = <I::GenericArgs as SliceLike>::IntoIter;
323
324    fn into_iter(self) -> Self::IntoIter {
325        self.var_values.iter()
326    }
327}
328
329impl<I: Interner> Index<ty::BoundVar> for CanonicalVarValues<I> {
330    type Output = I::GenericArg;
331
332    fn index(&self, value: ty::BoundVar) -> &I::GenericArg {
333        &self.var_values.as_slice()[value.as_usize()]
334    }
335}
rustc_type_ir/canonical.rs

rustc_type_ir/
canonical.rs
