rustc_infer/infer/canonical/mod.rs
1//! **Canonicalization** is the key to constructing a query in the
2//! middle of type inference. Ordinarily, it is not possible to store
3//! types from type inference in query keys, because they contain
4//! references to inference variables whose lifetimes are too short
5//! and so forth. Canonicalizing a value T1 using `canonicalize_query`
6//! produces two things:
7//!
8//! - a value T2 where each unbound inference variable has been
9//! replaced with a **canonical variable**;
10//! - a map M (of type `CanonicalVarValues`) from those canonical
11//! variables back to the original.
12//!
13//! We can then do queries using T2. These will give back constraints
14//! on the canonical variables which can be translated, using the map
15//! M, into constraints in our source context. This process of
16//! translating the results back is done by the
17//! `instantiate_query_result` method.
18//!
19//! For a more detailed look at what is happening here, check
20//! out the [chapter in the rustc dev guide][c].
21//!
22//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
23
24pub use instantiate::CanonicalExt;
25use rustc_index::IndexVec;
26pub use rustc_middle::infer::canonical::*;
27use rustc_middle::ty::{self, GenericArg, List, Ty, TyCtxt, TypeFoldable};
28use rustc_span::Span;
29
30use crate::infer::{InferCtxt, RegionVariableOrigin};
31
32mod canonicalizer;
33mod instantiate;
34pub mod query_response;
35
36impl<'tcx> InferCtxt<'tcx> {
37 /// Creates an instantiation S for the canonical value with fresh inference
38 /// variables and placeholders then applies it to the canonical value.
39 /// Returns both the instantiated result *and* the instantiation S.
40 ///
41 /// This can be invoked as part of constructing an
42 /// inference context at the start of a query (see
43 /// `InferCtxtBuilder::build_with_canonical`). It basically
44 /// brings the canonical value "into scope" within your new infcx.
45 ///
46 /// At the end of processing, the instantiation S (once
47 /// canonicalized) then represents the values that you computed
48 /// for each of the canonical inputs to your query.
49 pub fn instantiate_canonical<T>(
50 &self,
51 span: Span,
52 canonical: &Canonical<'tcx, T>,
53 ) -> (T, CanonicalVarValues<'tcx>)
54 where
55 T: TypeFoldable<TyCtxt<'tcx>>,
56 {
57 // For each universe that is referred to in the incoming
58 // query, create a universe in our local inference context. In
59 // practice, as of this writing, all queries have no universes
60 // in them, so this code has no effect, but it is looking
61 // forward to the day when we *do* want to carry universes
62 // through into queries.
63 //
64 // Instantiate the root-universe content into the current universe,
65 // and create fresh universes for the higher universes.
66 let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(self.universe())
67 .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
68 .collect();
69
70 let canonical_inference_vars =
71 self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
72 let result = canonical.instantiate(self.tcx, &canonical_inference_vars);
73 (result, canonical_inference_vars)
74 }
75
76 /// Given the "infos" about the canonical variables from some
77 /// canonical, creates fresh variables with the same
78 /// characteristics (see `instantiate_canonical_var` for
79 /// details). You can then use `instantiate` to instantiate the
80 /// canonical variable with these inference variables.
81 fn instantiate_canonical_vars(
82 &self,
83 span: Span,
84 variables: &List<CanonicalVarInfo<'tcx>>,
85 universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
86 ) -> CanonicalVarValues<'tcx> {
87 CanonicalVarValues {
88 var_values: self.tcx.mk_args_from_iter(
89 variables
90 .iter()
91 .map(|info| self.instantiate_canonical_var(span, info, &universe_map)),
92 ),
93 }
94 }
95
96 /// Given the "info" about a canonical variable, creates a fresh
97 /// variable for it. If this is an existentially quantified
98 /// variable, then you'll get a new inference variable; if it is a
99 /// universally quantified variable, you get a placeholder.
100 ///
101 /// FIXME(-Znext-solver): This is public because it's used by the
102 /// new trait solver which has a different canonicalization routine.
103 /// We should somehow deduplicate all of this.
104 pub fn instantiate_canonical_var(
105 &self,
106 span: Span,
107 cv_info: CanonicalVarInfo<'tcx>,
108 universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
109 ) -> GenericArg<'tcx> {
110 match cv_info.kind {
111 CanonicalVarKind::Ty(ty_kind) => {
112 let ty = match ty_kind {
113 CanonicalTyVarKind::General(ui) => {
114 self.next_ty_var_in_universe(span, universe_map(ui))
115 }
116
117 CanonicalTyVarKind::Int => self.next_int_var(),
118
119 CanonicalTyVarKind::Float => self.next_float_var(),
120 };
121 ty.into()
122 }
123
124 CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, bound }) => {
125 let universe_mapped = universe_map(universe);
126 let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, bound };
127 Ty::new_placeholder(self.tcx, placeholder_mapped).into()
128 }
129
130 CanonicalVarKind::Region(ui) => self
131 .next_region_var_in_universe(
132 RegionVariableOrigin::MiscVariable(span),
133 universe_map(ui),
134 )
135 .into(),
136
137 CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, bound }) => {
138 let universe_mapped = universe_map(universe);
139 let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, bound };
140 ty::Region::new_placeholder(self.tcx, placeholder_mapped).into()
141 }
142
143 CanonicalVarKind::Const(ui) => {
144 self.next_const_var_in_universe(span, universe_map(ui)).into()
145 }
146 CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, bound }) => {
147 let universe_mapped = universe_map(universe);
148 let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, bound };
149 ty::Const::new_placeholder(self.tcx, placeholder_mapped).into()
150 }
151 }
152 }
153}