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::data_structures::HashMap;
11use crate::inherent::*;
12use crate::{self as ty, Interner, TypingMode, UniverseIndex};
13
14#[derive_where(Clone, Hash, PartialEq, Debug; I: Interner, V)]
15#[derive_where(Copy; I: Interner, V: Copy)]
16#[cfg_attr(
17    feature = "nightly",
18    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
19)]
20pub struct CanonicalQueryInput<I: Interner, V> {
21    pub canonical: Canonical<I, V>,
22    pub typing_mode: TypingMode<I>,
23}
24
25impl<I: Interner, V: Eq> Eq for CanonicalQueryInput<I, V> {}
26
27/// A "canonicalized" type `V` is one where all free inference
28/// variables have been rewritten to "canonical vars". These are
29/// numbered starting from 0 in order of first appearance.
30#[derive_where(Clone, Hash, PartialEq, Debug; I: Interner, V)]
31#[derive_where(Copy; I: Interner, V: Copy)]
32#[cfg_attr(
33    feature = "nightly",
34    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
35)]
36pub struct Canonical<I: Interner, V> {
37    pub value: V,
38    pub max_universe: UniverseIndex,
39    pub variables: I::CanonicalVarKinds,
40}
41
42impl<I: Interner, V: Eq> Eq for Canonical<I, V> {}
43
44impl<I: Interner, V> Canonical<I, V> {
45    /// Allows you to map the `value` of a canonical while keeping the
46    /// same set of bound variables.
47    ///
48    /// **WARNING:** This function is very easy to mis-use, hence the
49    /// name!  In particular, the new value `W` must use all **the
50    /// same type/region variables** in **precisely the same order**
51    /// as the original! (The ordering is defined by the
52    /// `TypeFoldable` implementation of the type in question.)
53    ///
54    /// An example of a **correct** use of this:
55    ///
56    /// ```rust,ignore (not real code)
57    /// let a: Canonical<I, T> = ...;
58    /// let b: Canonical<I, (T,)> = a.unchecked_map(|v| (v, ));
59    /// ```
60    ///
61    /// An example of an **incorrect** use of this:
62    ///
63    /// ```rust,ignore (not real code)
64    /// let a: Canonical<I, T> = ...;
65    /// let ty: Ty<I> = ...;
66    /// let b: Canonical<I, (T, Ty<I>)> = a.unchecked_map(|v| (v, ty));
67    /// ```
68    pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<I, W> {
69        let Canonical { max_universe, variables, value } = self;
70        Canonical { max_universe, variables, value: map_op(value) }
71    }
72}
73
74impl<I: Interner, V: fmt::Display> fmt::Display for Canonical<I, V> {
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        let Self { value, max_universe, variables } = self;
77        write!(
78            f,
79            "Canonical {{ value: {value}, max_universe: {max_universe:?}, variables: {variables:?} }}",
80        )
81    }
82}
83
84/// Information about a canonical variable that is included with the
85/// canonical value. This is sufficient information for code to create
86/// a copy of the canonical value in some other inference context,
87/// with fresh inference variables replacing the canonical values.
88#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
89#[cfg_attr(
90    feature = "nightly",
91    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
92)]
93pub enum CanonicalVarKind<I: Interner> {
94    /// Some kind of type inference variable.
95    Ty(CanonicalTyVarKind),
96
97    /// A "placeholder" that represents "any type".
98    PlaceholderTy(I::PlaceholderTy),
99
100    /// Region variable `'?R`.
101    Region(UniverseIndex),
102
103    /// A "placeholder" that represents "any region". Created when you
104    /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
105    /// bound region `'a`.
106    PlaceholderRegion(I::PlaceholderRegion),
107
108    /// Some kind of const inference variable.
109    Const(UniverseIndex),
110
111    /// A "placeholder" that represents "any const".
112    PlaceholderConst(I::PlaceholderConst),
113}
114
115impl<I: Interner> Eq for CanonicalVarKind<I> {}
116
117impl<I: Interner> CanonicalVarKind<I> {
118    pub fn universe(self) -> UniverseIndex {
119        match self {
120            CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)) => ui,
121            CanonicalVarKind::Region(ui) => ui,
122            CanonicalVarKind::Const(ui) => ui,
123            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe(),
124            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe(),
125            CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe(),
126            CanonicalVarKind::Ty(CanonicalTyVarKind::Float | CanonicalTyVarKind::Int) => {
127                UniverseIndex::ROOT
128            }
129        }
130    }
131
132    /// Replaces the universe of this canonical variable with `ui`.
133    ///
134    /// In case this is a float or int variable, this causes an ICE if
135    /// the updated universe is not the root.
136    pub fn with_updated_universe(self, ui: UniverseIndex) -> CanonicalVarKind<I> {
137        match self {
138            CanonicalVarKind::Ty(CanonicalTyVarKind::General(_)) => {
139                CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui))
140            }
141            CanonicalVarKind::Region(_) => CanonicalVarKind::Region(ui),
142            CanonicalVarKind::Const(_) => CanonicalVarKind::Const(ui),
143
144            CanonicalVarKind::PlaceholderTy(placeholder) => {
145                CanonicalVarKind::PlaceholderTy(placeholder.with_updated_universe(ui))
146            }
147            CanonicalVarKind::PlaceholderRegion(placeholder) => {
148                CanonicalVarKind::PlaceholderRegion(placeholder.with_updated_universe(ui))
149            }
150            CanonicalVarKind::PlaceholderConst(placeholder) => {
151                CanonicalVarKind::PlaceholderConst(placeholder.with_updated_universe(ui))
152            }
153            CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => {
154                assert_eq!(ui, UniverseIndex::ROOT);
155                self
156            }
157        }
158    }
159
160    pub fn is_existential(self) -> bool {
161        match self {
162            CanonicalVarKind::Ty(_) => true,
163            CanonicalVarKind::PlaceholderTy(_) => false,
164            CanonicalVarKind::Region(_) => true,
165            CanonicalVarKind::PlaceholderRegion(..) => false,
166            CanonicalVarKind::Const(_) => true,
167            CanonicalVarKind::PlaceholderConst(_) => false,
168        }
169    }
170
171    pub fn is_region(self) -> bool {
172        match self {
173            CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => true,
174            CanonicalVarKind::Ty(_)
175            | CanonicalVarKind::PlaceholderTy(_)
176            | CanonicalVarKind::Const(_)
177            | CanonicalVarKind::PlaceholderConst(_) => false,
178        }
179    }
180
181    pub fn expect_placeholder_index(self) -> usize {
182        match self {
183            CanonicalVarKind::Ty(_) | CanonicalVarKind::Region(_) | CanonicalVarKind::Const(_) => {
184                panic!("expected placeholder: {self:?}")
185            }
186
187            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.var().as_usize(),
188            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.var().as_usize(),
189            CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.var().as_usize(),
190        }
191    }
192}
193
194/// Rust actually has more than one category of type variables;
195/// notably, the type variables we create for literals (e.g., 22 or
196/// 22.) can only be instantiated with integral/float types (e.g.,
197/// usize or f32). In order to faithfully reproduce a type, we need to
198/// know what set of types a given type variable can be unified with.
199#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
200#[cfg_attr(
201    feature = "nightly",
202    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
203)]
204pub enum CanonicalTyVarKind {
205    /// General type variable `?T` that can be unified with arbitrary types.
206    General(UniverseIndex),
207
208    /// Integral type variable `?I` (that can only be unified with integral types).
209    Int,
210
211    /// Floating-point type variable `?F` (that can only be unified with float types).
212    Float,
213}
214
215/// A set of values corresponding to the canonical variables from some
216/// `Canonical`. You can give these values to
217/// `canonical_value.instantiate` to instantiate them into the canonical
218/// value at the right places.
219///
220/// When you canonicalize a value `V`, you get back one of these
221/// vectors with the original values that were replaced by canonical
222/// variables. You will need to supply it later to instantiate the
223/// canonicalized query response.
224#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
225#[cfg_attr(
226    feature = "nightly",
227    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
228)]
229#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
230pub struct CanonicalVarValues<I: Interner> {
231    pub var_values: I::GenericArgs,
232}
233
234impl<I: Interner> Eq for CanonicalVarValues<I> {}
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}
336
337#[derive_where(Clone, Debug; I: Interner)]
338pub struct CanonicalParamEnvCacheEntry<I: Interner> {
339    pub param_env: I::ParamEnv,
340    pub variables: Vec<I::GenericArg>,
341    pub variable_lookup_table: HashMap<I::GenericArg, usize>,
342    pub var_kinds: Vec<CanonicalVarKind<I>>,
343}
rustc_type_ir/canonical.rs

rustc_type_ir/
canonical.rs
