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#[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 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#[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 Ty { ui: UniverseIndex, sub_root: ty::BoundVar },
100
101 Int,
103
104 Float,
106
107 PlaceholderTy(I::PlaceholderTy),
109
110 Region(UniverseIndex),
112
113 PlaceholderRegion(I::PlaceholderRegion),
117
118 Const(UniverseIndex),
120
121 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 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#[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::BoundVarIndexKind::Canonical, br) if br.var().as_usize() == bv)
234 }
235 ty::GenericArgKind::Type(ty) => {
236 matches!(ty.kind(), ty::Bound(ty::BoundVarIndexKind::Canonical, bt) if bt.var().as_usize() == bv)
237 }
238 ty::GenericArgKind::Const(ct) => {
239 matches!(ct.kind(), ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, 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::BoundVarIndexKind::Canonical, br) if var == br.var())
250 {
251 var = var + 1;
252 } else {
253 }
255 }
256 ty::GenericArgKind::Type(ty) => {
257 if matches!(ty.kind(), ty::Bound(ty::BoundVarIndexKind::Canonical, bt) if var == bt.var())
258 {
259 var = var + 1;
260 } else {
261 return false;
262 }
263 }
264 ty::GenericArgKind::Const(ct) => {
265 if matches!(ct.kind(), ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, bc) if var == bc.var())
266 {
267 var = var + 1;
268 } else {
269 return false;
270 }
271 }
272 }
273 }
274
275 true
276 }
277
278 pub fn make_identity(cx: I, infos: I::CanonicalVarKinds) -> CanonicalVarValues<I> {
281 CanonicalVarValues {
282 var_values: cx.mk_args_from_iter(infos.iter().enumerate().map(
283 |(i, kind)| -> I::GenericArg {
284 match kind {
285 CanonicalVarKind::Ty { .. }
286 | CanonicalVarKind::Int
287 | CanonicalVarKind::Float
288 | CanonicalVarKind::PlaceholderTy(_) => {
289 Ty::new_canonical_bound(cx, ty::BoundVar::from_usize(i)).into()
290 }
291 CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
292 Region::new_canonical_bound(cx, ty::BoundVar::from_usize(i)).into()
293 }
294 CanonicalVarKind::Const(_) | CanonicalVarKind::PlaceholderConst(_) => {
295 Const::new_canonical_bound(cx, ty::BoundVar::from_usize(i)).into()
296 }
297 }
298 },
299 )),
300 }
301 }
302
303 pub fn dummy() -> CanonicalVarValues<I> {
306 CanonicalVarValues { var_values: Default::default() }
307 }
308
309 pub fn instantiate(
310 cx: I,
311 variables: I::CanonicalVarKinds,
312 mut f: impl FnMut(&[I::GenericArg], CanonicalVarKind<I>) -> I::GenericArg,
313 ) -> CanonicalVarValues<I> {
314 if variables.len() <= 4 {
317 let mut var_values = ArrayVec::<_, 4>::new();
318 for info in variables.iter() {
319 var_values.push(f(&var_values, info));
320 }
321 CanonicalVarValues { var_values: cx.mk_args(&var_values) }
322 } else {
323 CanonicalVarValues::instantiate_cold(cx, variables, f)
324 }
325 }
326
327 #[cold]
328 fn instantiate_cold(
329 cx: I,
330 variables: I::CanonicalVarKinds,
331 mut f: impl FnMut(&[I::GenericArg], CanonicalVarKind<I>) -> I::GenericArg,
332 ) -> CanonicalVarValues<I> {
333 let mut var_values = Vec::with_capacity(variables.len());
334 for info in variables.iter() {
335 var_values.push(f(&var_values, info));
336 }
337 CanonicalVarValues { var_values: cx.mk_args(&var_values) }
338 }
339
340 #[inline]
341 pub fn len(&self) -> usize {
342 self.var_values.len()
343 }
344}
345
346impl<'a, I: Interner> IntoIterator for &'a CanonicalVarValues<I> {
347 type Item = I::GenericArg;
348 type IntoIter = <I::GenericArgs as SliceLike>::IntoIter;
349
350 fn into_iter(self) -> Self::IntoIter {
351 self.var_values.iter()
352 }
353}
354
355impl<I: Interner> Index<ty::BoundVar> for CanonicalVarValues<I> {
356 type Output = I::GenericArg;
357
358 fn index(&self, value: ty::BoundVar) -> &I::GenericArg {
359 &self.var_values.as_slice()[value.as_usize()]
360 }
361}
362
363#[derive_where(Clone, Debug; I: Interner)]
364pub struct CanonicalParamEnvCacheEntry<I: Interner> {
365 pub param_env: I::ParamEnv,
366 pub variables: Vec<I::GenericArg>,
367 pub variable_lookup_table: HashMap<I::GenericArg, usize>,
368 pub var_kinds: Vec<CanonicalVarKind<I>>,
369}