rustc_type_ir/
canonical.rs

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

rustc_type_ir/
canonical.rs
