]>
Commit | Line | Data |
---|---|---|
74b04a01 XL |
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 | |
ba9703b0 | 20 | //! out the [chapter in the rustc dev guide][c]. |
74b04a01 | 21 | //! |
f9f354fc | 22 | //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html |
74b04a01 XL |
23 | |
24 | use crate::infer::{ConstVariableOrigin, ConstVariableOriginKind}; | |
25 | use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin, TypeVariableOriginKind}; | |
74b04a01 | 26 | use rustc_index::vec::IndexVec; |
ba9703b0 XL |
27 | use rustc_middle::ty::fold::TypeFoldable; |
28 | use rustc_middle::ty::subst::GenericArg; | |
29 | use rustc_middle::ty::{self, BoundVar, List}; | |
74b04a01 XL |
30 | use rustc_span::source_map::Span; |
31 | ||
ba9703b0 | 32 | pub use rustc_middle::infer::canonical::*; |
74b04a01 XL |
33 | use substitute::CanonicalExt; |
34 | ||
35 | mod canonicalizer; | |
36 | pub mod query_response; | |
37 | mod substitute; | |
38 | ||
39 | impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { | |
40 | /// Creates a substitution S for the canonical value with fresh | |
41 | /// inference variables and applies it to the canonical value. | |
42 | /// Returns both the instantiated result *and* the substitution S. | |
43 | /// | |
44 | /// This is only meant to be invoked as part of constructing an | |
45 | /// inference context at the start of a query (see | |
46 | /// `InferCtxtBuilder::enter_with_canonical`). It basically | |
47 | /// brings the canonical value "into scope" within your new infcx. | |
48 | /// | |
49 | /// At the end of processing, the substitution S (once | |
50 | /// canonicalized) then represents the values that you computed | |
51 | /// for each of the canonical inputs to your query. | |
52 | ||
53 | pub fn instantiate_canonical_with_fresh_inference_vars<T>( | |
54 | &self, | |
55 | span: Span, | |
56 | canonical: &Canonical<'tcx, T>, | |
57 | ) -> (T, CanonicalVarValues<'tcx>) | |
58 | where | |
59 | T: TypeFoldable<'tcx>, | |
60 | { | |
61 | // For each universe that is referred to in the incoming | |
62 | // query, create a universe in our local inference context. In | |
63 | // practice, as of this writing, all queries have no universes | |
64 | // in them, so this code has no effect, but it is looking | |
65 | // forward to the day when we *do* want to carry universes | |
66 | // through into queries. | |
67 | let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT) | |
68 | .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe())) | |
69 | .collect(); | |
70 | ||
71 | let canonical_inference_vars = | |
72 | self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]); | |
73 | let result = canonical.substitute(self.tcx, &canonical_inference_vars); | |
74 | (result, canonical_inference_vars) | |
75 | } | |
76 | ||
77 | /// Given the "infos" about the canonical variables from some | |
78 | /// canonical, creates fresh variables with the same | |
79 | /// characteristics (see `instantiate_canonical_var` for | |
80 | /// details). You can then use `substitute` to instantiate the | |
81 | /// canonical variable with these inference variables. | |
82 | fn instantiate_canonical_vars( | |
83 | &self, | |
84 | span: Span, | |
85 | variables: &List<CanonicalVarInfo>, | |
86 | universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, | |
87 | ) -> CanonicalVarValues<'tcx> { | |
88 | let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables | |
89 | .iter() | |
f9f354fc | 90 | .map(|info| self.instantiate_canonical_var(span, info, &universe_map)) |
74b04a01 XL |
91 | .collect(); |
92 | ||
93 | CanonicalVarValues { var_values } | |
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 | fn instantiate_canonical_var( | |
101 | &self, | |
102 | span: Span, | |
103 | cv_info: CanonicalVarInfo, | |
104 | universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, | |
105 | ) -> GenericArg<'tcx> { | |
106 | match cv_info.kind { | |
107 | CanonicalVarKind::Ty(ty_kind) => { | |
108 | let ty = match ty_kind { | |
109 | CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe( | |
110 | TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span }, | |
111 | universe_map(ui), | |
112 | ), | |
113 | ||
114 | CanonicalTyVarKind::Int => self.next_int_var(), | |
115 | ||
116 | CanonicalTyVarKind::Float => self.next_float_var(), | |
117 | }; | |
118 | ty.into() | |
119 | } | |
120 | ||
121 | CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => { | |
122 | let universe_mapped = universe_map(universe); | |
123 | let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name }; | |
124 | self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into() | |
125 | } | |
126 | ||
127 | CanonicalVarKind::Region(ui) => self | |
128 | .next_region_var_in_universe( | |
129 | RegionVariableOrigin::MiscVariable(span), | |
130 | universe_map(ui), | |
131 | ) | |
132 | .into(), | |
133 | ||
134 | CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => { | |
135 | let universe_mapped = universe_map(universe); | |
136 | let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name }; | |
137 | self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into() | |
138 | } | |
139 | ||
140 | CanonicalVarKind::Const(ui) => self | |
141 | .next_const_var_in_universe( | |
142 | self.next_ty_var_in_universe( | |
143 | TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span }, | |
144 | universe_map(ui), | |
145 | ), | |
146 | ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span }, | |
147 | universe_map(ui), | |
148 | ) | |
149 | .into(), | |
150 | ||
151 | CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }) => { | |
152 | let universe_mapped = universe_map(universe); | |
153 | let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name }; | |
154 | self.tcx | |
155 | .mk_const(ty::Const { | |
156 | val: ty::ConstKind::Placeholder(placeholder_mapped), | |
157 | ty: self.tcx.types.err, // FIXME(const_generics) | |
158 | }) | |
159 | .into() | |
160 | } | |
161 | } | |
162 | } | |
163 | } |