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

rustc_type_ir/
canonical.rs
