]>
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; | |
9ffffee4 | 29 | use rustc_middle::ty::{self, List, TyCtxt}; |
74b04a01 XL |
30 | use rustc_span::source_map::Span; |
31 | ||
ba9703b0 | 32 | pub use rustc_middle::infer::canonical::*; |
9ffffee4 | 33 | pub use substitute::CanonicalExt; |
74b04a01 XL |
34 | |
35 | mod canonicalizer; | |
36 | pub mod query_response; | |
37 | mod substitute; | |
38 | ||
2b03887a | 39 | impl<'tcx> InferCtxt<'tcx> { |
74b04a01 XL |
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 | /// | |
487cf647 | 44 | /// This can be invoked as part of constructing an |
74b04a01 | 45 | /// inference context at the start of a query (see |
487cf647 | 46 | /// `InferCtxtBuilder::build_with_canonical`). It basically |
74b04a01 XL |
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. | |
74b04a01 XL |
52 | pub fn instantiate_canonical_with_fresh_inference_vars<T>( |
53 | &self, | |
54 | span: Span, | |
55 | canonical: &Canonical<'tcx, T>, | |
56 | ) -> (T, CanonicalVarValues<'tcx>) | |
57 | where | |
9ffffee4 | 58 | T: TypeFoldable<TyCtxt<'tcx>>, |
74b04a01 XL |
59 | { |
60 | // For each universe that is referred to in the incoming | |
61 | // query, create a universe in our local inference context. In | |
62 | // practice, as of this writing, all queries have no universes | |
63 | // in them, so this code has no effect, but it is looking | |
64 | // forward to the day when we *do* want to carry universes | |
65 | // through into queries. | |
487cf647 FG |
66 | // |
67 | // Instantiate the root-universe content into the current universe, | |
68 | // and create fresh universes for the higher universes. | |
69 | let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(self.universe()) | |
70 | .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe())) | |
74b04a01 XL |
71 | .collect(); |
72 | ||
73 | let canonical_inference_vars = | |
74 | self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]); | |
75 | let result = canonical.substitute(self.tcx, &canonical_inference_vars); | |
76 | (result, canonical_inference_vars) | |
77 | } | |
78 | ||
79 | /// Given the "infos" about the canonical variables from some | |
80 | /// canonical, creates fresh variables with the same | |
81 | /// characteristics (see `instantiate_canonical_var` for | |
82 | /// details). You can then use `substitute` to instantiate the | |
83 | /// canonical variable with these inference variables. | |
84 | fn instantiate_canonical_vars( | |
85 | &self, | |
86 | span: Span, | |
fc512014 | 87 | variables: &List<CanonicalVarInfo<'tcx>>, |
74b04a01 XL |
88 | universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, |
89 | ) -> CanonicalVarValues<'tcx> { | |
9ffffee4 FG |
90 | CanonicalVarValues { |
91 | var_values: self.tcx.mk_substs_from_iter( | |
92 | variables | |
93 | .iter() | |
94 | .map(|info| self.instantiate_canonical_var(span, info, &universe_map)), | |
95 | ), | |
96 | } | |
74b04a01 XL |
97 | } |
98 | ||
99 | /// Given the "info" about a canonical variable, creates a fresh | |
100 | /// variable for it. If this is an existentially quantified | |
101 | /// variable, then you'll get a new inference variable; if it is a | |
102 | /// universally quantified variable, you get a placeholder. | |
9ffffee4 FG |
103 | /// |
104 | /// FIXME(-Ztrait-solver=next): This is public because it's used by the | |
105 | /// new trait solver which has a different canonicalization routine. | |
106 | /// We should somehow deduplicate all of this. | |
107 | pub fn instantiate_canonical_var( | |
74b04a01 XL |
108 | &self, |
109 | span: Span, | |
fc512014 | 110 | cv_info: CanonicalVarInfo<'tcx>, |
74b04a01 XL |
111 | universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, |
112 | ) -> GenericArg<'tcx> { | |
113 | match cv_info.kind { | |
114 | CanonicalVarKind::Ty(ty_kind) => { | |
115 | let ty = match ty_kind { | |
116 | CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe( | |
117 | TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span }, | |
118 | universe_map(ui), | |
119 | ), | |
120 | ||
121 | CanonicalTyVarKind::Int => self.next_int_var(), | |
122 | ||
123 | CanonicalTyVarKind::Float => self.next_float_var(), | |
124 | }; | |
125 | ty.into() | |
126 | } | |
127 | ||
128 | CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => { | |
129 | let universe_mapped = universe_map(universe); | |
130 | let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name }; | |
9ffffee4 | 131 | self.tcx.mk_placeholder(placeholder_mapped).into() |
74b04a01 XL |
132 | } |
133 | ||
134 | CanonicalVarKind::Region(ui) => self | |
135 | .next_region_var_in_universe( | |
136 | RegionVariableOrigin::MiscVariable(span), | |
137 | universe_map(ui), | |
138 | ) | |
139 | .into(), | |
140 | ||
141 | CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => { | |
142 | let universe_mapped = universe_map(universe); | |
143 | let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name }; | |
9ffffee4 | 144 | self.tcx.mk_re_placeholder(placeholder_mapped).into() |
74b04a01 XL |
145 | } |
146 | ||
5099ac24 | 147 | CanonicalVarKind::Const(ui, ty) => self |
74b04a01 | 148 | .next_const_var_in_universe( |
5099ac24 | 149 | ty, |
74b04a01 XL |
150 | ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span }, |
151 | universe_map(ui), | |
152 | ) | |
153 | .into(), | |
154 | ||
064997fb | 155 | CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }, ty) => { |
74b04a01 XL |
156 | let universe_mapped = universe_map(universe); |
157 | let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name }; | |
487cf647 | 158 | self.tcx.mk_const(placeholder_mapped, ty).into() |
74b04a01 XL |
159 | } |
160 | } | |
161 | } | |
162 | } |