1use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack};
2use rustc_type_ir::inherent::*;
3use rustc_type_ir::solve::{Goal, QueryInput};
4use rustc_type_ir::{
5 self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalTyVarKind, CanonicalVarKind,
6 Flags, InferCtxtLike, Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable,
7 TypeVisitableExt,
8};
9
10use crate::delegate::SolverDelegate;
11
12const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits(
14 TypeFlags::HAS_INFER.bits()
15 | TypeFlags::HAS_PLACEHOLDER.bits()
16 | TypeFlags::HAS_PARAM.bits()
17 | TypeFlags::HAS_FREE_REGIONS.bits()
18 | TypeFlags::HAS_RE_ERASED.bits(),
19)
20.unwrap();
21
22#[derive(Debug, Clone, Copy)]
28enum CanonicalizeMode {
29 Input { keep_static: bool },
33 Response {
41 max_input_universe: ty::UniverseIndex,
51 },
52}
53
54pub struct Canonicalizer<'a, D: SolverDelegate<Interner = I>, I: Interner> {
55 delegate: &'a D,
56
57 canonicalize_mode: CanonicalizeMode,
59
60 variables: &'a mut Vec<I::GenericArg>,
62 var_kinds: Vec<CanonicalVarKind<I>>,
63 variable_lookup_table: HashMap<I::GenericArg, usize>,
64 binder_index: ty::DebruijnIndex,
65
66 cache: HashMap<(ty::DebruijnIndex, I::Ty), I::Ty>,
70}
71
72impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
73 pub fn canonicalize_response<T: TypeFoldable<I>>(
74 delegate: &'a D,
75 max_input_universe: ty::UniverseIndex,
76 variables: &'a mut Vec<I::GenericArg>,
77 value: T,
78 ) -> ty::Canonical<I, T> {
79 let mut canonicalizer = Canonicalizer {
80 delegate,
81 canonicalize_mode: CanonicalizeMode::Response { max_input_universe },
82
83 variables,
84 variable_lookup_table: Default::default(),
85 var_kinds: Vec::new(),
86 binder_index: ty::INNERMOST,
87
88 cache: Default::default(),
89 };
90
91 let value = if value.has_type_flags(NEEDS_CANONICAL) {
92 value.fold_with(&mut canonicalizer)
93 } else {
94 value
95 };
96 debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
97 debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
98 let (max_universe, variables) = canonicalizer.finalize();
99 Canonical { max_universe, variables, value }
100 }
101
102 fn canonicalize_param_env(
103 delegate: &'a D,
104 variables: &'a mut Vec<I::GenericArg>,
105 param_env: I::ParamEnv,
106 ) -> (I::ParamEnv, HashMap<I::GenericArg, usize>, Vec<CanonicalVarKind<I>>) {
107 if !param_env.has_type_flags(NEEDS_CANONICAL) {
108 return (param_env, Default::default(), Vec::new());
109 }
110
111 if !param_env.has_non_region_infer() {
119 delegate.cx().canonical_param_env_cache_get_or_insert(
120 param_env,
121 || {
122 let mut variables = Vec::new();
123 let mut env_canonicalizer = Canonicalizer {
124 delegate,
125 canonicalize_mode: CanonicalizeMode::Input { keep_static: true },
126
127 variables: &mut variables,
128 variable_lookup_table: Default::default(),
129 var_kinds: Vec::new(),
130 binder_index: ty::INNERMOST,
131
132 cache: Default::default(),
133 };
134 let param_env = param_env.fold_with(&mut env_canonicalizer);
135 debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
136 CanonicalParamEnvCacheEntry {
137 param_env,
138 variable_lookup_table: env_canonicalizer.variable_lookup_table,
139 var_kinds: env_canonicalizer.var_kinds,
140 variables,
141 }
142 },
143 |&CanonicalParamEnvCacheEntry {
144 param_env,
145 variables: ref cache_variables,
146 ref variable_lookup_table,
147 ref var_kinds,
148 }| {
149 debug_assert!(variables.is_empty());
150 variables.extend(cache_variables.iter().copied());
151 (param_env, variable_lookup_table.clone(), var_kinds.clone())
152 },
153 )
154 } else {
155 let mut env_canonicalizer = Canonicalizer {
156 delegate,
157 canonicalize_mode: CanonicalizeMode::Input { keep_static: true },
158
159 variables,
160 variable_lookup_table: Default::default(),
161 var_kinds: Vec::new(),
162 binder_index: ty::INNERMOST,
163
164 cache: Default::default(),
165 };
166 let param_env = param_env.fold_with(&mut env_canonicalizer);
167 debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
168 (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds)
169 }
170 }
171
172 pub fn canonicalize_input<P: TypeFoldable<I>>(
181 delegate: &'a D,
182 variables: &'a mut Vec<I::GenericArg>,
183 input: QueryInput<I, P>,
184 ) -> ty::Canonical<I, QueryInput<I, P>> {
185 let (param_env, variable_lookup_table, var_kinds) =
187 Canonicalizer::canonicalize_param_env(delegate, variables, input.goal.param_env);
188 let mut rest_canonicalizer = Canonicalizer {
191 delegate,
192 canonicalize_mode: CanonicalizeMode::Input { keep_static: false },
193
194 variables,
195 variable_lookup_table,
196 var_kinds,
197 binder_index: ty::INNERMOST,
198
199 cache: Default::default(),
205 };
206
207 let predicate = input.goal.predicate;
208 let predicate = if predicate.has_type_flags(NEEDS_CANONICAL) {
209 predicate.fold_with(&mut rest_canonicalizer)
210 } else {
211 predicate
212 };
213 let goal = Goal { param_env, predicate };
214
215 let predefined_opaques_in_body = input.predefined_opaques_in_body;
216 let predefined_opaques_in_body =
217 if input.predefined_opaques_in_body.has_type_flags(NEEDS_CANONICAL) {
218 predefined_opaques_in_body.fold_with(&mut rest_canonicalizer)
219 } else {
220 predefined_opaques_in_body
221 };
222
223 let value = QueryInput { goal, predefined_opaques_in_body };
224
225 debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
226 debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
227 let (max_universe, variables) = rest_canonicalizer.finalize();
228 Canonical { max_universe, variables, value }
229 }
230
231 fn get_or_insert_bound_var(
232 &mut self,
233 arg: impl Into<I::GenericArg>,
234 kind: CanonicalVarKind<I>,
235 ) -> ty::BoundVar {
236 let arg = arg.into();
239 let idx = if self.variables.len() > 16 {
240 if self.variable_lookup_table.is_empty() {
241 self.variable_lookup_table.extend(self.variables.iter().copied().zip(0..));
242 }
243
244 *self.variable_lookup_table.entry(arg).or_insert_with(|| {
245 let var = self.variables.len();
246 self.variables.push(arg);
247 self.var_kinds.push(kind);
248 var
249 })
250 } else {
251 self.variables.iter().position(|&v| v == arg).unwrap_or_else(|| {
252 let var = self.variables.len();
253 self.variables.push(arg);
254 self.var_kinds.push(kind);
255 var
256 })
257 };
258
259 ty::BoundVar::from(idx)
260 }
261
262 fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) {
263 let mut var_kinds = self.var_kinds;
264 match self.canonicalize_mode {
267 CanonicalizeMode::Input { .. } => {
269 debug_assert!(
270 var_kinds.iter().all(|var| var.universe() == ty::UniverseIndex::ROOT),
271 "expected all vars to be canonicalized in root universe: {var_kinds:#?}"
272 );
273 let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds);
274 (ty::UniverseIndex::ROOT, var_kinds)
275 }
276 CanonicalizeMode::Response { max_input_universe } => {
281 for var in var_kinds.iter_mut() {
282 let uv = var.universe();
283 let new_uv = ty::UniverseIndex::from(
284 uv.index().saturating_sub(max_input_universe.index()),
285 );
286 *var = var.with_updated_universe(new_uv);
287 }
288 let max_universe = var_kinds
289 .iter()
290 .map(|kind| kind.universe())
291 .max()
292 .unwrap_or(ty::UniverseIndex::ROOT);
293 let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds);
294 (max_universe, var_kinds)
295 }
296 }
297 }
298
299 fn cached_fold_ty(&mut self, t: I::Ty) -> I::Ty {
300 let kind = match t.kind() {
301 ty::Infer(i) => match i {
302 ty::TyVar(vid) => {
303 debug_assert_eq!(
304 self.delegate.opportunistic_resolve_ty_var(vid),
305 t,
306 "ty vid should have been resolved fully before canonicalization"
307 );
308
309 match self.canonicalize_mode {
310 CanonicalizeMode::Input { .. } => CanonicalVarKind::Ty(
311 CanonicalTyVarKind::General(ty::UniverseIndex::ROOT),
312 ),
313 CanonicalizeMode::Response { .. } => {
314 CanonicalVarKind::Ty(CanonicalTyVarKind::General(
315 self.delegate.universe_of_ty(vid).unwrap_or_else(|| {
316 panic!("ty var should have been resolved: {t:?}")
317 }),
318 ))
319 }
320 }
321 }
322 ty::IntVar(vid) => {
323 debug_assert_eq!(
324 self.delegate.opportunistic_resolve_int_var(vid),
325 t,
326 "ty vid should have been resolved fully before canonicalization"
327 );
328 CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
329 }
330 ty::FloatVar(vid) => {
331 debug_assert_eq!(
332 self.delegate.opportunistic_resolve_float_var(vid),
333 t,
334 "ty vid should have been resolved fully before canonicalization"
335 );
336 CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
337 }
338 ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
339 panic!("fresh vars not expected in canonicalization")
340 }
341 },
342 ty::Placeholder(placeholder) => match self.canonicalize_mode {
343 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
344 PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
345 ),
346 CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
347 },
348 ty::Param(_) => match self.canonicalize_mode {
349 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
350 PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
351 ),
352 CanonicalizeMode::Response { .. } => panic!("param ty in response: {t:?}"),
353 },
354 ty::Bool
355 | ty::Char
356 | ty::Int(_)
357 | ty::Uint(_)
358 | ty::Float(_)
359 | ty::Adt(_, _)
360 | ty::Foreign(_)
361 | ty::Str
362 | ty::Array(_, _)
363 | ty::Slice(_)
364 | ty::RawPtr(_, _)
365 | ty::Ref(_, _, _)
366 | ty::Pat(_, _)
367 | ty::FnDef(_, _)
368 | ty::FnPtr(..)
369 | ty::UnsafeBinder(_)
370 | ty::Dynamic(_, _, _)
371 | ty::Closure(..)
372 | ty::CoroutineClosure(..)
373 | ty::Coroutine(_, _)
374 | ty::CoroutineWitness(..)
375 | ty::Never
376 | ty::Tuple(_)
377 | ty::Alias(_, _)
378 | ty::Bound(_, _)
379 | ty::Error(_) => {
380 return if t.has_type_flags(NEEDS_CANONICAL) {
381 ensure_sufficient_stack(|| t.super_fold_with(self))
382 } else {
383 t
384 };
385 }
386 };
387
388 let var = self.get_or_insert_bound_var(t, kind);
389
390 Ty::new_anon_bound(self.cx(), self.binder_index, var)
391 }
392}
393
394impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicalizer<'_, D, I> {
395 fn cx(&self) -> I {
396 self.delegate.cx()
397 }
398
399 fn fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T>
400 where
401 T: TypeFoldable<I>,
402 {
403 self.binder_index.shift_in(1);
404 let t = t.super_fold_with(self);
405 self.binder_index.shift_out(1);
406 t
407 }
408
409 fn fold_region(&mut self, r: I::Region) -> I::Region {
410 let kind = match r.kind() {
411 ty::ReBound(..) => return r,
412
413 ty::ReStatic => match self.canonicalize_mode {
416 CanonicalizeMode::Input { keep_static: false } => {
417 CanonicalVarKind::Region(ty::UniverseIndex::ROOT)
418 }
419 CanonicalizeMode::Input { keep_static: true }
420 | CanonicalizeMode::Response { .. } => return r,
421 },
422
423 ty::ReErased | ty::ReError(_) => match self.canonicalize_mode {
431 CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
432 CanonicalizeMode::Response { .. } => return r,
433 },
434
435 ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode {
436 CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
437 CanonicalizeMode::Response { .. } => {
438 panic!("unexpected region in response: {r:?}")
439 }
440 },
441
442 ty::RePlaceholder(placeholder) => match self.canonicalize_mode {
443 CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
445 CanonicalizeMode::Response { max_input_universe } => {
446 if max_input_universe.can_name(placeholder.universe()) {
449 panic!("new placeholder in universe {max_input_universe:?}: {r:?}");
450 }
451 CanonicalVarKind::PlaceholderRegion(placeholder)
452 }
453 },
454
455 ty::ReVar(vid) => {
456 debug_assert_eq!(
457 self.delegate.opportunistic_resolve_lt_var(vid),
458 r,
459 "region vid should have been resolved fully before canonicalization"
460 );
461 match self.canonicalize_mode {
462 CanonicalizeMode::Input { keep_static: _ } => {
463 CanonicalVarKind::Region(ty::UniverseIndex::ROOT)
464 }
465 CanonicalizeMode::Response { .. } => {
466 CanonicalVarKind::Region(self.delegate.universe_of_lt(vid).unwrap())
467 }
468 }
469 }
470 };
471
472 let var = self.get_or_insert_bound_var(r, kind);
473
474 Region::new_anon_bound(self.cx(), self.binder_index, var)
475 }
476
477 fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
478 if let Some(&ty) = self.cache.get(&(self.binder_index, t)) {
479 ty
480 } else {
481 let res = self.cached_fold_ty(t);
482 let old = self.cache.insert((self.binder_index, t), res);
483 assert_eq!(old, None);
484 res
485 }
486 }
487
488 fn fold_const(&mut self, c: I::Const) -> I::Const {
489 let kind = match c.kind() {
490 ty::ConstKind::Infer(i) => match i {
491 ty::InferConst::Var(vid) => {
492 debug_assert_eq!(
493 self.delegate.opportunistic_resolve_ct_var(vid),
494 c,
495 "const vid should have been resolved fully before canonicalization"
496 );
497
498 match self.canonicalize_mode {
499 CanonicalizeMode::Input { .. } => {
500 CanonicalVarKind::Const(ty::UniverseIndex::ROOT)
501 }
502 CanonicalizeMode::Response { .. } => {
503 CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap())
504 }
505 }
506 }
507 ty::InferConst::Fresh(_) => todo!(),
508 },
509 ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode {
510 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
511 PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
512 ),
513 CanonicalizeMode::Response { .. } => {
514 CanonicalVarKind::PlaceholderConst(placeholder)
515 }
516 },
517 ty::ConstKind::Param(_) => match self.canonicalize_mode {
518 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
519 PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
520 ),
521 CanonicalizeMode::Response { .. } => panic!("param ty in response: {c:?}"),
522 },
523 ty::ConstKind::Bound(_, _)
525 | ty::ConstKind::Unevaluated(_)
526 | ty::ConstKind::Value(_)
527 | ty::ConstKind::Error(_)
528 | ty::ConstKind::Expr(_) => {
529 return if c.has_type_flags(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c };
530 }
531 };
532
533 let var = self.get_or_insert_bound_var(c, kind);
534
535 Const::new_anon_bound(self.cx(), self.binder_index, var)
536 }
537
538 fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
539 if p.flags().intersects(NEEDS_CANONICAL) { p.super_fold_with(self) } else { p }
540 }
541
542 fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses {
543 match self.canonicalize_mode {
544 CanonicalizeMode::Input { keep_static: true }
545 | CanonicalizeMode::Response { max_input_universe: _ } => {}
546 CanonicalizeMode::Input { keep_static: false } => {
547 panic!("erasing 'static in env")
548 }
549 }
550 if c.flags().intersects(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c }
551 }
552}