1 //! This module contains the "canonicalizer" itself.
3 //! For an overview of what canonicalization is and how it fits into
4 //! rustc, check out the [chapter in the rustc dev guide][c].
6 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
8 use crate::infer::canonical::{
9 Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, Canonicalized,
12 use crate::infer::InferCtxt;
13 use rustc_middle::ty::flags::FlagComputation;
14 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
15 use rustc_middle::ty::subst::GenericArg;
16 use rustc_middle::ty::{self, BoundVar, InferConst, List, Ty, TyCtxt, TypeFlags};
17 use std::sync::atomic::Ordering;
19 use rustc_data_structures::fx::FxHashMap;
20 use rustc_index::vec::Idx;
21 use smallvec::SmallVec;
23 impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
24 /// Canonicalizes a query value `V`. When we canonicalize a query,
25 /// we not only canonicalize unbound inference variables, but we
26 /// *also* replace all free regions whatsoever. So for example a
27 /// query like `T: Trait<'static>` would be canonicalized to
33 /// with a mapping M that maps `'?0` to `'static`.
35 /// To get a good understanding of what is happening here, check
36 /// out the [chapter in the rustc dev guide][c].
38 /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query
39 pub fn canonicalize_query<V>(
42 query_state: &mut OriginalQueryValues<'tcx>,
43 ) -> Canonicalized<'tcx, V>
45 V: TypeFoldable<'tcx>,
47 self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
49 Canonicalizer::canonicalize(value, self, self.tcx, &CanonicalizeAllFreeRegions, query_state)
52 /// Like [Self::canonicalize_query], but preserves distinct universes. For
53 /// example, canonicalizing `&'?0: Trait<'?1>`, where `'?0` is in `U1` and
54 /// `'?1` is in `U3` would be canonicalized to have ?0` in `U1` and `'?1`
57 /// This is used for Chalk integration.
58 pub fn canonicalize_query_preserving_universes<V>(
61 query_state: &mut OriginalQueryValues<'tcx>,
62 ) -> Canonicalized<'tcx, V>
64 V: TypeFoldable<'tcx>,
66 self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
68 Canonicalizer::canonicalize(
72 &CanonicalizeAllFreeRegionsPreservingUniverses,
77 /// Canonicalizes a query *response* `V`. When we canonicalize a
78 /// query response, we only canonicalize unbound inference
79 /// variables, and we leave other free regions alone. So,
80 /// continuing with the example from `canonicalize_query`, if
81 /// there was an input query `T: Trait<'static>`, it would have
82 /// been canonicalized to
88 /// with a mapping M that maps `'?0` to `'static`. But if we found that there
89 /// exists only one possible impl of `Trait`, and it looks like
91 /// impl<T> Trait<'static> for T { .. }
93 /// then we would prepare a query result R that (among other
94 /// things) includes a mapping to `'?0 := 'static`. When
95 /// canonicalizing this query result R, we would leave this
96 /// reference to `'static` alone.
98 /// To get a good understanding of what is happening here, check
99 /// out the [chapter in the rustc dev guide][c].
101 /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query-result
102 pub fn canonicalize_response<V>(&self, value: V) -> Canonicalized<'tcx, V>
104 V: TypeFoldable<'tcx>,
106 let mut query_state = OriginalQueryValues::default();
107 Canonicalizer::canonicalize(
111 &CanonicalizeQueryResponse,
116 pub fn canonicalize_user_type_annotation<V>(&self, value: V) -> Canonicalized<'tcx, V>
118 V: TypeFoldable<'tcx>,
120 let mut query_state = OriginalQueryValues::default();
121 Canonicalizer::canonicalize(
125 &CanonicalizeUserTypeAnnotation,
130 /// A variant of `canonicalize_query` that does not
131 /// canonicalize `'static`. This is useful when
132 /// the query implementation can perform more efficient
133 /// handling of `'static` regions (e.g. trait evaluation).
134 pub fn canonicalize_query_keep_static<V>(
137 query_state: &mut OriginalQueryValues<'tcx>,
138 ) -> Canonicalized<'tcx, V>
140 V: TypeFoldable<'tcx>,
142 self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
144 Canonicalizer::canonicalize(
148 &CanonicalizeFreeRegionsOtherThanStatic,
154 /// Controls how we canonicalize "free regions" that are not inference
155 /// variables. This depends on what we are canonicalizing *for* --
156 /// e.g., if we are canonicalizing to create a query, we want to
157 /// replace those with inference variables, since we want to make a
158 /// maximally general query. But if we are canonicalizing a *query
159 /// response*, then we don't typically replace free regions, as they
160 /// must have been introduced from other parts of the system.
161 trait CanonicalizeMode {
162 fn canonicalize_free_region<'tcx>(
164 canonicalizer: &mut Canonicalizer<'_, 'tcx>,
166 ) -> ty::Region<'tcx>;
168 fn any(&self) -> bool;
170 // Do we preserve universe of variables.
171 fn preserve_universes(&self) -> bool;
174 struct CanonicalizeQueryResponse;
176 impl CanonicalizeMode for CanonicalizeQueryResponse {
177 fn canonicalize_free_region<'tcx>(
179 canonicalizer: &mut Canonicalizer<'_, 'tcx>,
181 ) -> ty::Region<'tcx> {
186 | ty::ReEmpty(ty::UniverseIndex::ROOT)
187 | ty::ReEarlyBound(..) => r,
189 ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
190 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(placeholder) },
195 let universe = canonicalizer.region_var_universe(vid);
196 canonicalizer.canonical_var_for_region(
197 CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) },
203 bug!("canonicalizing 'empty in universe {:?}", ui) // FIXME
207 // Other than `'static` or `'empty`, the query
208 // response should be executing in a fully
209 // canonicalized environment, so there shouldn't be
210 // any other region names it can come up.
212 // rust-lang/rust#57464: `impl Trait` can leak local
213 // scopes (in manner violating typeck). Therefore, use
214 // `delay_span_bug` to allow type error over an ICE.
215 ty::tls::with(|tcx| {
216 tcx.sess.delay_span_bug(
217 rustc_span::DUMMY_SP,
218 &format!("unexpected region in query response: `{:?}`", r),
226 fn any(&self) -> bool {
230 fn preserve_universes(&self) -> bool {
235 struct CanonicalizeUserTypeAnnotation;
237 impl CanonicalizeMode for CanonicalizeUserTypeAnnotation {
238 fn canonicalize_free_region<'tcx>(
240 canonicalizer: &mut Canonicalizer<'_, 'tcx>,
242 ) -> ty::Region<'tcx> {
244 ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r,
245 ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
247 // We only expect region names that the user can type.
248 bug!("unexpected region in query response: `{:?}`", r)
253 fn any(&self) -> bool {
257 fn preserve_universes(&self) -> bool {
262 struct CanonicalizeAllFreeRegions;
264 impl CanonicalizeMode for CanonicalizeAllFreeRegions {
265 fn canonicalize_free_region<'tcx>(
267 canonicalizer: &mut Canonicalizer<'_, 'tcx>,
269 ) -> ty::Region<'tcx> {
270 canonicalizer.canonical_var_for_region_in_root_universe(r)
273 fn any(&self) -> bool {
277 fn preserve_universes(&self) -> bool {
282 struct CanonicalizeAllFreeRegionsPreservingUniverses;
284 impl CanonicalizeMode for CanonicalizeAllFreeRegionsPreservingUniverses {
285 fn canonicalize_free_region<'tcx>(
287 canonicalizer: &mut Canonicalizer<'_, 'tcx>,
289 ) -> ty::Region<'tcx> {
290 let universe = canonicalizer.infcx.universe_of_region(r);
291 canonicalizer.canonical_var_for_region(
292 CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) },
297 fn any(&self) -> bool {
301 fn preserve_universes(&self) -> bool {
306 struct CanonicalizeFreeRegionsOtherThanStatic;
308 impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic {
309 fn canonicalize_free_region<'tcx>(
311 canonicalizer: &mut Canonicalizer<'_, 'tcx>,
313 ) -> ty::Region<'tcx> {
314 if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) }
317 fn any(&self) -> bool {
321 fn preserve_universes(&self) -> bool {
326 struct Canonicalizer<'cx, 'tcx> {
327 infcx: &'cx InferCtxt<'cx, 'tcx>,
329 variables: SmallVec<[CanonicalVarInfo<'tcx>; 8]>,
330 query_state: &'cx mut OriginalQueryValues<'tcx>,
331 // Note that indices is only used once `var_values` is big enough to be
333 indices: FxHashMap<GenericArg<'tcx>, BoundVar>,
334 canonicalize_mode: &'cx dyn CanonicalizeMode,
335 needs_canonical_flags: TypeFlags,
337 binder_index: ty::DebruijnIndex,
340 impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
341 fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
345 fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
347 T: TypeFoldable<'tcx>,
349 self.binder_index.shift_in(1);
350 let t = t.super_fold_with(self);
351 self.binder_index.shift_out(1);
355 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
357 ty::ReLateBound(index, ..) => {
358 if index >= self.binder_index {
359 bug!("escaping late-bound region during canonicalization");
366 let resolved_vid = self
370 .unwrap_region_constraints()
371 .opportunistic_resolve_var(vid);
373 "canonical: region var found with vid {:?}, \
374 opportunistically resolved to {:?}",
377 let r = self.tcx.reuse_or_mk_region(r, ty::ReVar(resolved_vid));
378 self.canonicalize_mode.canonicalize_free_region(self, r)
382 | ty::ReEarlyBound(..)
385 | ty::RePlaceholder(..)
386 | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r),
390 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
392 ty::Infer(ty::TyVar(vid)) => {
393 debug!("canonical: type var found with vid {:?}", vid);
394 match self.infcx.probe_ty_var(vid) {
395 // `t` could be a float / int variable; canonicalize that instead.
397 debug!("(resolved to {:?})", t);
401 // `TyVar(vid)` is unresolved, track its universe index in the canonicalized
404 if !self.canonicalize_mode.preserve_universes() {
405 // FIXME: perf problem described in #55921.
406 ui = ty::UniverseIndex::ROOT;
408 self.canonicalize_ty_var(
410 kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
418 ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(
419 CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int) },
423 ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(
424 CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float) },
428 ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
429 bug!("encountered a fresh type during canonicalization")
432 ty::Placeholder(placeholder) => self.canonicalize_ty_var(
433 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderTy(placeholder) },
437 ty::Bound(debruijn, _) => {
438 if debruijn >= self.binder_index {
439 bug!("escaping bound type during canonicalization")
447 | ty::GeneratorWitness(..)
468 | ty::Opaque(..) => {
469 if t.flags().intersects(self.needs_canonical_flags) {
470 t.super_fold_with(self)
478 fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
480 ty::ConstKind::Infer(InferConst::Var(vid)) => {
481 debug!("canonical: const var found with vid {:?}", vid);
482 match self.infcx.probe_const_var(vid) {
484 debug!("(resolved to {:?})", c);
485 return self.fold_const(c);
488 // `ConstVar(vid)` is unresolved, track its universe index in the
489 // canonicalized result
491 if !self.canonicalize_mode.preserve_universes() {
492 // FIXME: perf problem described in #55921.
493 ui = ty::UniverseIndex::ROOT;
495 return self.canonicalize_const_var(
496 CanonicalVarInfo { kind: CanonicalVarKind::Const(ui, ct.ty()) },
502 ty::ConstKind::Infer(InferConst::Fresh(_)) => {
503 bug!("encountered a fresh const during canonicalization")
505 ty::ConstKind::Bound(debruijn, _) => {
506 if debruijn >= self.binder_index {
507 bug!("escaping bound type during canonicalization")
512 ty::ConstKind::Placeholder(placeholder) => {
513 return self.canonicalize_const_var(
514 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderConst(placeholder) },
521 let flags = FlagComputation::for_const(ct);
522 if flags.intersects(self.needs_canonical_flags) { ct.super_fold_with(self) } else { ct }
526 impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
527 /// The main `canonicalize` method, shared impl of
528 /// `canonicalize_query` and `canonicalize_response`.
531 infcx: &InferCtxt<'_, 'tcx>,
533 canonicalize_region_mode: &dyn CanonicalizeMode,
534 query_state: &mut OriginalQueryValues<'tcx>,
535 ) -> Canonicalized<'tcx, V>
537 V: TypeFoldable<'tcx>,
539 let needs_canonical_flags = if canonicalize_region_mode.any() {
540 TypeFlags::NEEDS_INFER |
541 TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS`
542 TypeFlags::HAS_TY_PLACEHOLDER |
543 TypeFlags::HAS_CT_PLACEHOLDER
545 TypeFlags::NEEDS_INFER
546 | TypeFlags::HAS_RE_PLACEHOLDER
547 | TypeFlags::HAS_TY_PLACEHOLDER
548 | TypeFlags::HAS_CT_PLACEHOLDER
551 // Fast path: nothing that needs to be canonicalized.
552 if !value.has_type_flags(needs_canonical_flags) {
553 let canon_value = Canonical {
554 max_universe: ty::UniverseIndex::ROOT,
555 variables: List::empty(),
561 let mut canonicalizer = Canonicalizer {
564 canonicalize_mode: canonicalize_region_mode,
565 needs_canonical_flags,
566 variables: SmallVec::new(),
568 indices: FxHashMap::default(),
569 binder_index: ty::INNERMOST,
571 let out_value = value.fold_with(&mut canonicalizer);
573 // Once we have canonicalized `out_value`, it should not
574 // contain anything that ties it to this inference context
576 debug_assert!(!out_value.needs_infer() && !out_value.has_placeholders());
578 let canonical_variables =
579 tcx.intern_canonical_var_infos(&canonicalizer.universe_canonicalized_variables());
581 let max_universe = canonical_variables
583 .map(|cvar| cvar.universe())
585 .unwrap_or(ty::UniverseIndex::ROOT);
587 Canonical { max_universe, variables: canonical_variables, value: out_value }
590 /// Creates a canonical variable replacing `kind` from the input,
591 /// or returns an existing variable if `kind` has already been
592 /// seen. `kind` is expected to be an unbound variable (or
593 /// potentially a free region).
594 fn canonical_var(&mut self, info: CanonicalVarInfo<'tcx>, kind: GenericArg<'tcx>) -> BoundVar {
595 let Canonicalizer { variables, query_state, indices, .. } = self;
597 let var_values = &mut query_state.var_values;
599 let universe = info.universe();
600 if universe != ty::UniverseIndex::ROOT {
601 assert!(self.canonicalize_mode.preserve_universes());
603 // Insert universe into the universe map. To preserve the order of the
604 // universes in the value being canonicalized, we don't update the
605 // universe in `info` until we have finished canonicalizing.
606 match query_state.universe_map.binary_search(&universe) {
607 Err(idx) => query_state.universe_map.insert(idx, universe),
612 // This code is hot. `variables` and `var_values` are usually small
613 // (fewer than 8 elements ~95% of the time). They are SmallVec's to
614 // avoid allocations in those cases. We also don't use `indices` to
615 // determine if a kind has been seen before until the limit of 8 has
616 // been exceeded, to also avoid allocations for `indices`.
617 if !var_values.spilled() {
618 // `var_values` is stack-allocated. `indices` isn't used yet. Do a
619 // direct linear search of `var_values`.
620 if let Some(idx) = var_values.iter().position(|&k| k == kind) {
621 // `kind` is already present in `var_values`.
624 // `kind` isn't present in `var_values`. Append it. Likewise
625 // for `info` and `variables`.
626 variables.push(info);
627 var_values.push(kind);
628 assert_eq!(variables.len(), var_values.len());
630 // If `var_values` has become big enough to be heap-allocated,
631 // fill up `indices` to facilitate subsequent lookups.
632 if var_values.spilled() {
633 assert!(indices.is_empty());
634 *indices = var_values
637 .map(|(i, &kind)| (kind, BoundVar::new(i)))
640 // The cv is the index of the appended element.
641 BoundVar::new(var_values.len() - 1)
644 // `var_values` is large. Do a hashmap search via `indices`.
645 *indices.entry(kind).or_insert_with(|| {
646 variables.push(info);
647 var_values.push(kind);
648 assert_eq!(variables.len(), var_values.len());
649 BoundVar::new(variables.len() - 1)
654 /// Replaces the universe indexes used in `var_values` with their index in
655 /// `query_state.universe_map`. This minimizes the maximum universe used in
656 /// the canonicalized value.
657 fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarInfo<'tcx>; 8]> {
658 if self.query_state.universe_map.len() == 1 {
659 return self.variables;
662 let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self
667 .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx)))
672 .map(|v| CanonicalVarInfo {
674 CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => {
677 CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => {
678 CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u]))
680 CanonicalVarKind::Region(u) => {
681 CanonicalVarKind::Region(reverse_universe_map[&u])
683 CanonicalVarKind::Const(u, t) => {
684 CanonicalVarKind::Const(reverse_universe_map[&u], t)
686 CanonicalVarKind::PlaceholderTy(placeholder) => {
687 CanonicalVarKind::PlaceholderTy(ty::Placeholder {
688 universe: reverse_universe_map[&placeholder.universe],
692 CanonicalVarKind::PlaceholderRegion(placeholder) => {
693 CanonicalVarKind::PlaceholderRegion(ty::Placeholder {
694 universe: reverse_universe_map[&placeholder.universe],
698 CanonicalVarKind::PlaceholderConst(placeholder) => {
699 CanonicalVarKind::PlaceholderConst(ty::Placeholder {
700 universe: reverse_universe_map[&placeholder.universe],
709 /// Shorthand helper that creates a canonical region variable for
710 /// `r` (always in the root universe). The reason that we always
711 /// put these variables into the root universe is because this
712 /// method is used during **query construction:** in that case, we
713 /// are taking all the regions and just putting them into the most
714 /// generic context we can. This may generate solutions that don't
715 /// fit (e.g., that equate some region variable with a placeholder
716 /// it can't name) on the caller side, but that's ok, the caller
717 /// can figure that out. In the meantime, it maximizes our
720 /// (This works because unification never fails -- and hence trait
721 /// selection is never affected -- due to a universe mismatch.)
722 fn canonical_var_for_region_in_root_universe(
725 ) -> ty::Region<'tcx> {
726 self.canonical_var_for_region(
727 CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT) },
732 /// Returns the universe in which `vid` is defined.
733 fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex {
734 self.infcx.inner.borrow_mut().unwrap_region_constraints().var_universe(vid)
737 /// Creates a canonical variable (with the given `info`)
738 /// representing the region `r`; return a region referencing it.
739 fn canonical_var_for_region(
741 info: CanonicalVarInfo<'tcx>,
743 ) -> ty::Region<'tcx> {
744 let var = self.canonical_var(info, r.into());
745 let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32()) };
746 let region = ty::ReLateBound(self.binder_index, br);
747 self.tcx().mk_region(region)
750 /// Given a type variable `ty_var` of the given kind, first check
751 /// if `ty_var` is bound to anything; if so, canonicalize
752 /// *that*. Otherwise, create a new canonical variable for
754 fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo<'tcx>, ty_var: Ty<'tcx>) -> Ty<'tcx> {
755 let infcx = self.infcx;
756 let bound_to = infcx.shallow_resolve(ty_var);
757 if bound_to != ty_var {
758 self.fold_ty(bound_to)
760 let var = self.canonical_var(info, ty_var.into());
761 self.tcx().mk_ty(ty::Bound(self.binder_index, var.into()))
765 /// Given a type variable `const_var` of the given kind, first check
766 /// if `const_var` is bound to anything; if so, canonicalize
767 /// *that*. Otherwise, create a new canonical variable for
769 fn canonicalize_const_var(
771 info: CanonicalVarInfo<'tcx>,
772 const_var: ty::Const<'tcx>,
773 ) -> ty::Const<'tcx> {
774 let infcx = self.infcx;
775 let bound_to = infcx.shallow_resolve(const_var);
776 if bound_to != const_var {
777 self.fold_const(bound_to)
779 let var = self.canonical_var(info, const_var.into());
780 self.tcx().mk_const(ty::ConstS {
781 val: ty::ConstKind::Bound(self.binder_index, var),
782 ty: self.fold_ty(const_var.ty()),