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

rustc_type_ir/
canonical.rs
