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

rustc_type_ir/
canonical.rs
