rustc_type_ir/
canonical.rs

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

rustc_type_ir/
canonical.rs
