1use std::cmp::Ordering;
2
3use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack};
4use rustc_type_ir::inherent::*;
5use rustc_type_ir::solve::{Goal, QueryInput};
6use rustc_type_ir::{
7 self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalTyVarKind, CanonicalVarKind,
8 Flags, InferCtxtLike, Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable,
9 TypeVisitableExt,
10};
11
12use crate::delegate::SolverDelegate;
13
14const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits(
16 TypeFlags::HAS_INFER.bits()
17 | TypeFlags::HAS_PLACEHOLDER.bits()
18 | TypeFlags::HAS_PARAM.bits()
19 | TypeFlags::HAS_FREE_REGIONS.bits()
20 | TypeFlags::HAS_RE_ERASED.bits(),
21)
22.unwrap();
23
24#[derive(Debug, Clone, Copy)]
30enum CanonicalizeMode {
31 Input { keep_static: bool },
35 Response {
43 max_input_universe: ty::UniverseIndex,
53 },
54}
55
56pub struct Canonicalizer<'a, D: SolverDelegate<Interner = I>, I: Interner> {
57 delegate: &'a D,
58
59 canonicalize_mode: CanonicalizeMode,
61
62 variables: &'a mut Vec<I::GenericArg>,
64 var_kinds: Vec<CanonicalVarKind<I>>,
65 variable_lookup_table: HashMap<I::GenericArg, usize>,
66 binder_index: ty::DebruijnIndex,
67
68 cache: HashMap<(ty::DebruijnIndex, I::Ty), I::Ty>,
72}
73
74impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
75 pub fn canonicalize_response<T: TypeFoldable<I>>(
76 delegate: &'a D,
77 max_input_universe: ty::UniverseIndex,
78 variables: &'a mut Vec<I::GenericArg>,
79 value: T,
80 ) -> ty::Canonical<I, T> {
81 let mut canonicalizer = Canonicalizer {
82 delegate,
83 canonicalize_mode: CanonicalizeMode::Response { max_input_universe },
84
85 variables,
86 variable_lookup_table: Default::default(),
87 var_kinds: Vec::new(),
88 binder_index: ty::INNERMOST,
89
90 cache: Default::default(),
91 };
92
93 let value = if value.has_type_flags(NEEDS_CANONICAL) {
94 value.fold_with(&mut canonicalizer)
95 } else {
96 value
97 };
98 debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
99 debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
100 let (max_universe, variables) = canonicalizer.finalize();
101 Canonical { max_universe, variables, value }
102 }
103
104 fn canonicalize_param_env(
105 delegate: &'a D,
106 variables: &'a mut Vec<I::GenericArg>,
107 param_env: I::ParamEnv,
108 ) -> (I::ParamEnv, HashMap<I::GenericArg, usize>, Vec<CanonicalVarKind<I>>) {
109 if !param_env.has_type_flags(NEEDS_CANONICAL) {
110 return (param_env, Default::default(), Vec::new());
111 }
112
113 if !param_env.has_non_region_infer() {
121 delegate.cx().canonical_param_env_cache_get_or_insert(
122 param_env,
123 || {
124 let mut variables = Vec::new();
125 let mut env_canonicalizer = Canonicalizer {
126 delegate,
127 canonicalize_mode: CanonicalizeMode::Input { keep_static: true },
128
129 variables: &mut variables,
130 variable_lookup_table: Default::default(),
131 var_kinds: Vec::new(),
132 binder_index: ty::INNERMOST,
133
134 cache: Default::default(),
135 };
136 let param_env = param_env.fold_with(&mut env_canonicalizer);
137 debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
138 CanonicalParamEnvCacheEntry {
139 param_env,
140 variable_lookup_table: env_canonicalizer.variable_lookup_table,
141 var_kinds: env_canonicalizer.var_kinds,
142 variables,
143 }
144 },
145 |&CanonicalParamEnvCacheEntry {
146 param_env,
147 variables: ref cache_variables,
148 ref variable_lookup_table,
149 ref var_kinds,
150 }| {
151 debug_assert!(variables.is_empty());
152 variables.extend(cache_variables.iter().copied());
153 (param_env, variable_lookup_table.clone(), var_kinds.clone())
154 },
155 )
156 } else {
157 let mut env_canonicalizer = Canonicalizer {
158 delegate,
159 canonicalize_mode: CanonicalizeMode::Input { keep_static: true },
160
161 variables,
162 variable_lookup_table: Default::default(),
163 var_kinds: Vec::new(),
164 binder_index: ty::INNERMOST,
165
166 cache: Default::default(),
167 };
168 let param_env = param_env.fold_with(&mut env_canonicalizer);
169 debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
170 (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds)
171 }
172 }
173
174 pub fn canonicalize_input<P: TypeFoldable<I>>(
183 delegate: &'a D,
184 variables: &'a mut Vec<I::GenericArg>,
185 input: QueryInput<I, P>,
186 ) -> ty::Canonical<I, QueryInput<I, P>> {
187 let (param_env, variable_lookup_table, var_kinds) =
189 Canonicalizer::canonicalize_param_env(delegate, variables, input.goal.param_env);
190 let mut rest_canonicalizer = Canonicalizer {
193 delegate,
194 canonicalize_mode: CanonicalizeMode::Input { keep_static: false },
195
196 variables,
197 variable_lookup_table,
198 var_kinds,
199 binder_index: ty::INNERMOST,
200
201 cache: Default::default(),
207 };
208
209 let predicate = input.goal.predicate;
210 let predicate = if predicate.has_type_flags(NEEDS_CANONICAL) {
211 predicate.fold_with(&mut rest_canonicalizer)
212 } else {
213 predicate
214 };
215 let goal = Goal { param_env, predicate };
216
217 let predefined_opaques_in_body = input.predefined_opaques_in_body;
218 let predefined_opaques_in_body =
219 if input.predefined_opaques_in_body.has_type_flags(NEEDS_CANONICAL) {
220 predefined_opaques_in_body.fold_with(&mut rest_canonicalizer)
221 } else {
222 predefined_opaques_in_body
223 };
224
225 let value = QueryInput { goal, predefined_opaques_in_body };
226
227 debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
228 debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
229 let (max_universe, variables) = rest_canonicalizer.finalize();
230 Canonical { max_universe, variables, value }
231 }
232
233 fn get_or_insert_bound_var(
234 &mut self,
235 arg: impl Into<I::GenericArg>,
236 kind: CanonicalVarKind<I>,
237 ) -> ty::BoundVar {
238 let arg = arg.into();
241 let idx = if self.variables.len() > 16 {
242 if self.variable_lookup_table.is_empty() {
243 self.variable_lookup_table.extend(self.variables.iter().copied().zip(0..));
244 }
245
246 *self.variable_lookup_table.entry(arg).or_insert_with(|| {
247 let var = self.variables.len();
248 self.variables.push(arg);
249 self.var_kinds.push(kind);
250 var
251 })
252 } else {
253 self.variables.iter().position(|&v| v == arg).unwrap_or_else(|| {
254 let var = self.variables.len();
255 self.variables.push(arg);
256 self.var_kinds.push(kind);
257 var
258 })
259 };
260
261 ty::BoundVar::from(idx)
262 }
263
264 fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) {
265 let mut var_kinds = self.var_kinds;
266 match self.canonicalize_mode {
269 CanonicalizeMode::Input { .. } => {}
274 CanonicalizeMode::Response { max_input_universe } => {
279 for var in var_kinds.iter_mut() {
280 let uv = var.universe();
281 let new_uv = ty::UniverseIndex::from(
282 uv.index().saturating_sub(max_input_universe.index()),
283 );
284 *var = var.with_updated_universe(new_uv);
285 }
286 let max_universe = var_kinds
287 .iter()
288 .map(|kind| kind.universe())
289 .max()
290 .unwrap_or(ty::UniverseIndex::ROOT);
291
292 let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds);
293 return (max_universe, var_kinds);
294 }
295 }
296
297 let mut curr_compressed_uv = ty::UniverseIndex::ROOT;
316 let mut existential_in_new_uv = None;
317 let mut next_orig_uv = Some(ty::UniverseIndex::ROOT);
318 while let Some(orig_uv) = next_orig_uv.take() {
319 let mut update_uv = |var: &mut CanonicalVarKind<I>, orig_uv, is_existential| {
320 let uv = var.universe();
321 match uv.cmp(&orig_uv) {
322 Ordering::Less => (), Ordering::Equal => {
324 if is_existential {
325 if existential_in_new_uv.is_some_and(|uv| uv < orig_uv) {
326 curr_compressed_uv = curr_compressed_uv.next_universe();
332 }
333
334 existential_in_new_uv = Some(orig_uv);
339 } else if existential_in_new_uv.is_some() {
340 curr_compressed_uv = curr_compressed_uv.next_universe();
347 existential_in_new_uv = None;
348 }
349
350 *var = var.with_updated_universe(curr_compressed_uv);
351 }
352 Ordering::Greater => {
353 if next_orig_uv.is_none_or(|curr_next_uv| uv.cannot_name(curr_next_uv)) {
359 next_orig_uv = Some(uv);
360 }
361 }
362 }
363 };
364
365 for is_existential in [false, true] {
371 for var in var_kinds.iter_mut() {
372 if !var.is_region() {
375 if is_existential == var.is_existential() {
376 update_uv(var, orig_uv, is_existential)
377 }
378 }
379 }
380 }
381 }
382
383 let mut first_region = true;
385 for var in var_kinds.iter_mut() {
386 if var.is_region() {
387 if first_region {
388 first_region = false;
389 curr_compressed_uv = curr_compressed_uv.next_universe();
390 }
391 debug_assert!(var.is_existential());
392 *var = var.with_updated_universe(curr_compressed_uv);
393 }
394 }
395
396 let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds);
397 (curr_compressed_uv, var_kinds)
398 }
399
400 fn cached_fold_ty(&mut self, t: I::Ty) -> I::Ty {
401 let kind = match t.kind() {
402 ty::Infer(i) => match i {
403 ty::TyVar(vid) => {
404 debug_assert_eq!(
405 self.delegate.opportunistic_resolve_ty_var(vid),
406 t,
407 "ty vid should have been resolved fully before canonicalization"
408 );
409
410 CanonicalVarKind::Ty(CanonicalTyVarKind::General(
411 self.delegate
412 .universe_of_ty(vid)
413 .unwrap_or_else(|| panic!("ty var should have been resolved: {t:?}")),
414 ))
415 }
416 ty::IntVar(vid) => {
417 debug_assert_eq!(
418 self.delegate.opportunistic_resolve_int_var(vid),
419 t,
420 "ty vid should have been resolved fully before canonicalization"
421 );
422 CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
423 }
424 ty::FloatVar(vid) => {
425 debug_assert_eq!(
426 self.delegate.opportunistic_resolve_float_var(vid),
427 t,
428 "ty vid should have been resolved fully before canonicalization"
429 );
430 CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
431 }
432 ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
433 panic!("fresh vars not expected in canonicalization")
434 }
435 },
436 ty::Placeholder(placeholder) => match self.canonicalize_mode {
437 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
438 PlaceholderLike::new_anon(placeholder.universe(), self.variables.len().into()),
439 ),
440 CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
441 },
442 ty::Param(_) => match self.canonicalize_mode {
443 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
444 PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
445 ),
446 CanonicalizeMode::Response { .. } => panic!("param ty in response: {t:?}"),
447 },
448 ty::Bool
449 | ty::Char
450 | ty::Int(_)
451 | ty::Uint(_)
452 | ty::Float(_)
453 | ty::Adt(_, _)
454 | ty::Foreign(_)
455 | ty::Str
456 | ty::Array(_, _)
457 | ty::Slice(_)
458 | ty::RawPtr(_, _)
459 | ty::Ref(_, _, _)
460 | ty::Pat(_, _)
461 | ty::FnDef(_, _)
462 | ty::FnPtr(..)
463 | ty::UnsafeBinder(_)
464 | ty::Dynamic(_, _, _)
465 | ty::Closure(..)
466 | ty::CoroutineClosure(..)
467 | ty::Coroutine(_, _)
468 | ty::CoroutineWitness(..)
469 | ty::Never
470 | ty::Tuple(_)
471 | ty::Alias(_, _)
472 | ty::Bound(_, _)
473 | ty::Error(_) => {
474 return if t.has_type_flags(NEEDS_CANONICAL) {
475 ensure_sufficient_stack(|| t.super_fold_with(self))
476 } else {
477 t
478 };
479 }
480 };
481
482 let var = self.get_or_insert_bound_var(t, kind);
483
484 Ty::new_anon_bound(self.cx(), self.binder_index, var)
485 }
486}
487
488impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicalizer<'_, D, I> {
489 fn cx(&self) -> I {
490 self.delegate.cx()
491 }
492
493 fn fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T>
494 where
495 T: TypeFoldable<I>,
496 {
497 self.binder_index.shift_in(1);
498 let t = t.super_fold_with(self);
499 self.binder_index.shift_out(1);
500 t
501 }
502
503 fn fold_region(&mut self, r: I::Region) -> I::Region {
504 let kind = match r.kind() {
505 ty::ReBound(..) => return r,
506
507 ty::ReStatic => match self.canonicalize_mode {
510 CanonicalizeMode::Input { keep_static: false } => {
511 CanonicalVarKind::Region(ty::UniverseIndex::ROOT)
512 }
513 CanonicalizeMode::Input { keep_static: true }
514 | CanonicalizeMode::Response { .. } => return r,
515 },
516
517 ty::ReErased | ty::ReError(_) => match self.canonicalize_mode {
525 CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
526 CanonicalizeMode::Response { .. } => return r,
527 },
528
529 ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode {
530 CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
531 CanonicalizeMode::Response { .. } => {
532 panic!("unexpected region in response: {r:?}")
533 }
534 },
535
536 ty::RePlaceholder(placeholder) => match self.canonicalize_mode {
537 CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
539 CanonicalizeMode::Response { max_input_universe } => {
540 if max_input_universe.can_name(placeholder.universe()) {
543 panic!("new placeholder in universe {max_input_universe:?}: {r:?}");
544 }
545 CanonicalVarKind::PlaceholderRegion(placeholder)
546 }
547 },
548
549 ty::ReVar(vid) => {
550 debug_assert_eq!(
551 self.delegate.opportunistic_resolve_lt_var(vid),
552 r,
553 "region vid should have been resolved fully before canonicalization"
554 );
555 match self.canonicalize_mode {
556 CanonicalizeMode::Input { keep_static: _ } => {
557 CanonicalVarKind::Region(ty::UniverseIndex::ROOT)
558 }
559 CanonicalizeMode::Response { .. } => {
560 CanonicalVarKind::Region(self.delegate.universe_of_lt(vid).unwrap())
561 }
562 }
563 }
564 };
565
566 let var = self.get_or_insert_bound_var(r, kind);
567
568 Region::new_anon_bound(self.cx(), self.binder_index, var)
569 }
570
571 fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
572 if let Some(&ty) = self.cache.get(&(self.binder_index, t)) {
573 ty
574 } else {
575 let res = self.cached_fold_ty(t);
576 let old = self.cache.insert((self.binder_index, t), res);
577 assert_eq!(old, None);
578 res
579 }
580 }
581
582 fn fold_const(&mut self, c: I::Const) -> I::Const {
583 let kind = match c.kind() {
584 ty::ConstKind::Infer(i) => match i {
585 ty::InferConst::Var(vid) => {
586 debug_assert_eq!(
587 self.delegate.opportunistic_resolve_ct_var(vid),
588 c,
589 "const vid should have been resolved fully before canonicalization"
590 );
591 CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap())
592 }
593 ty::InferConst::Fresh(_) => todo!(),
594 },
595 ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode {
596 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
597 PlaceholderLike::new_anon(placeholder.universe(), self.variables.len().into()),
598 ),
599 CanonicalizeMode::Response { .. } => {
600 CanonicalVarKind::PlaceholderConst(placeholder)
601 }
602 },
603 ty::ConstKind::Param(_) => match self.canonicalize_mode {
604 CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
605 PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
606 ),
607 CanonicalizeMode::Response { .. } => panic!("param ty in response: {c:?}"),
608 },
609 ty::ConstKind::Bound(_, _)
611 | ty::ConstKind::Unevaluated(_)
612 | ty::ConstKind::Value(_)
613 | ty::ConstKind::Error(_)
614 | ty::ConstKind::Expr(_) => {
615 return if c.has_type_flags(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c };
616 }
617 };
618
619 let var = self.get_or_insert_bound_var(c, kind);
620
621 Const::new_anon_bound(self.cx(), self.binder_index, var)
622 }
623
624 fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
625 if p.flags().intersects(NEEDS_CANONICAL) { p.super_fold_with(self) } else { p }
626 }
627
628 fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses {
629 match self.canonicalize_mode {
630 CanonicalizeMode::Input { keep_static: true }
631 | CanonicalizeMode::Response { max_input_universe: _ } => {}
632 CanonicalizeMode::Input { keep_static: false } => {
633 panic!("erasing 'static in env")
634 }
635 }
636 if c.flags().intersects(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c }
637 }
638}