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

rustc_type_ir/
canonical.rs
