]>
Commit | Line | Data |
---|---|---|
8faf50e0 XL |
1 | //! This module contains the code to instantiate a "query result", and |
2 | //! in particular to extract out the resulting region obligations and | |
3 | //! encode them therein. | |
4 | //! | |
5e7ed085 | 5 | //! For an overview of what canonicalization is and how it fits into |
ba9703b0 | 6 | //! rustc, check out the [chapter in the rustc dev guide][c]. |
8faf50e0 | 7 | //! |
f9f354fc | 8 | //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html |
8faf50e0 | 9 | |
74b04a01 | 10 | use crate::infer::canonical::substitute::{substitute_value, CanonicalExt}; |
9fa01778 | 11 | use crate::infer::canonical::{ |
dfeec247 XL |
12 | Canonical, CanonicalVarValues, CanonicalizedQueryResponse, Certainty, OriginalQueryValues, |
13 | QueryOutlivesConstraint, QueryRegionConstraints, QueryResponse, | |
8faf50e0 | 14 | }; |
74b04a01 | 15 | use crate::infer::nll_relate::{NormalizationStrategy, TypeRelating, TypeRelatingDelegate}; |
9fa01778 | 16 | use crate::infer::region_constraints::{Constraint, RegionConstraintData}; |
5869c6ff | 17 | use crate::infer::{InferCtxt, InferOk, InferResult, NllRegionVariableOrigin}; |
9fa01778 | 18 | use crate::traits::query::{Fallible, NoSolution}; |
9fa01778 | 19 | use crate::traits::{Obligation, ObligationCause, PredicateObligation}; |
2b03887a | 20 | use crate::traits::{PredicateObligations, TraitEngine}; |
dfeec247 XL |
21 | use rustc_data_structures::captures::Captures; |
22 | use rustc_index::vec::Idx; | |
23 | use rustc_index::vec::IndexVec; | |
ba9703b0 | 24 | use rustc_middle::arena::ArenaAllocatable; |
f2b60f7d | 25 | use rustc_middle::mir::ConstraintCategory; |
5e7ed085 | 26 | use rustc_middle::ty::error::TypeError; |
ba9703b0 XL |
27 | use rustc_middle::ty::fold::TypeFoldable; |
28 | use rustc_middle::ty::relate::TypeRelation; | |
29 | use rustc_middle::ty::subst::{GenericArg, GenericArgKind}; | |
f9f354fc | 30 | use rustc_middle::ty::{self, BoundVar, Const, ToPredicate, Ty, TyCtxt}; |
5e7ed085 | 31 | use rustc_span::Span; |
dfeec247 | 32 | use std::fmt::Debug; |
cdc7bbd5 | 33 | use std::iter; |
8faf50e0 | 34 | |
2b03887a | 35 | impl<'tcx> InferCtxt<'tcx> { |
8faf50e0 XL |
36 | /// This method is meant to be invoked as the final step of a canonical query |
37 | /// implementation. It is given: | |
38 | /// | |
39 | /// - the instantiated variables `inference_vars` created from the query key | |
40 | /// - the result `answer` of the query | |
41 | /// - a fulfillment context `fulfill_cx` that may contain various obligations which | |
42 | /// have yet to be proven. | |
43 | /// | |
44 | /// Given this, the function will process the obligations pending | |
45 | /// in `fulfill_cx`: | |
46 | /// | |
47 | /// - If all the obligations can be proven successfully, it will | |
48 | /// package up any resulting region obligations (extracted from | |
49 | /// `infcx`) along with the fully resolved value `answer` into a | |
50 | /// query result (which is then itself canonicalized). | |
51 | /// - If some obligations can be neither proven nor disproven, then | |
52 | /// the same thing happens, but the resulting query is marked as ambiguous. | |
53 | /// - Finally, if any of the obligations result in a hard error, | |
54 | /// then `Err(NoSolution)` is returned. | |
c295e0f8 | 55 | #[instrument(skip(self, inference_vars, answer, fulfill_cx), level = "trace")] |
0bf4aa26 | 56 | pub fn make_canonicalized_query_response<T>( |
8faf50e0 XL |
57 | &self, |
58 | inference_vars: CanonicalVarValues<'tcx>, | |
59 | answer: T, | |
0731742a | 60 | fulfill_cx: &mut dyn TraitEngine<'tcx>, |
dc9dc135 | 61 | ) -> Fallible<CanonicalizedQueryResponse<'tcx, T>> |
8faf50e0 | 62 | where |
dc9dc135 | 63 | T: Debug + TypeFoldable<'tcx>, |
f035d41b | 64 | Canonical<'tcx, QueryResponse<'tcx, T>>: ArenaAllocatable<'tcx>, |
8faf50e0 | 65 | { |
0bf4aa26 | 66 | let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?; |
f2b60f7d | 67 | debug!("query_response = {:#?}", query_response); |
fc512014 | 68 | let canonical_result = self.canonicalize_response(query_response); |
c295e0f8 | 69 | debug!("canonical_result = {:#?}", canonical_result); |
8faf50e0 | 70 | |
48663c56 | 71 | Ok(self.tcx.arena.alloc(canonical_result)) |
8faf50e0 XL |
72 | } |
73 | ||
0731742a XL |
74 | /// A version of `make_canonicalized_query_response` that does |
75 | /// not pack in obligations, for contexts that want to drop | |
76 | /// pending obligations instead of treating them as an ambiguity (e.g. | |
77 | /// typeck "probing" contexts). | |
78 | /// | |
79 | /// If you DO want to keep track of pending obligations (which | |
80 | /// include all region obligations, so this includes all cases | |
81 | /// that care about regions) with this function, you have to | |
9fa01778 | 82 | /// do it yourself, by e.g., having them be a part of the answer. |
0731742a XL |
83 | pub fn make_query_response_ignoring_pending_obligations<T>( |
84 | &self, | |
85 | inference_vars: CanonicalVarValues<'tcx>, | |
dc9dc135 XL |
86 | answer: T, |
87 | ) -> Canonical<'tcx, QueryResponse<'tcx, T>> | |
0731742a | 88 | where |
dc9dc135 | 89 | T: Debug + TypeFoldable<'tcx>, |
0731742a | 90 | { |
fc512014 | 91 | self.canonicalize_response(QueryResponse { |
0731742a | 92 | var_values: inference_vars, |
dc9dc135 | 93 | region_constraints: QueryRegionConstraints::default(), |
0731742a | 94 | certainty: Certainty::Proven, // Ambiguities are OK! |
5e7ed085 | 95 | opaque_types: vec![], |
0731742a XL |
96 | value: answer, |
97 | }) | |
98 | } | |
99 | ||
0bf4aa26 | 100 | /// Helper for `make_canonicalized_query_response` that does |
8faf50e0 | 101 | /// everything up until the final canonicalization. |
c295e0f8 | 102 | #[instrument(skip(self, fulfill_cx), level = "debug")] |
0bf4aa26 | 103 | fn make_query_response<T>( |
8faf50e0 XL |
104 | &self, |
105 | inference_vars: CanonicalVarValues<'tcx>, | |
106 | answer: T, | |
0731742a | 107 | fulfill_cx: &mut dyn TraitEngine<'tcx>, |
0bf4aa26 | 108 | ) -> Result<QueryResponse<'tcx, T>, NoSolution> |
8faf50e0 | 109 | where |
dc9dc135 | 110 | T: Debug + TypeFoldable<'tcx>, |
8faf50e0 XL |
111 | { |
112 | let tcx = self.tcx; | |
113 | ||
8faf50e0 | 114 | // Select everything, returning errors. |
3c0e092e | 115 | let true_errors = fulfill_cx.select_where_possible(self); |
8faf50e0 XL |
116 | debug!("true_errors = {:#?}", true_errors); |
117 | ||
118 | if !true_errors.is_empty() { | |
119 | // FIXME -- we don't indicate *why* we failed to solve | |
0bf4aa26 | 120 | debug!("make_query_response: true_errors={:#?}", true_errors); |
8faf50e0 XL |
121 | return Err(NoSolution); |
122 | } | |
123 | ||
124 | // Anything left unselected *now* must be an ambiguity. | |
3c0e092e | 125 | let ambig_errors = fulfill_cx.select_all_or_error(self); |
8faf50e0 XL |
126 | debug!("ambig_errors = {:#?}", ambig_errors); |
127 | ||
128 | let region_obligations = self.take_registered_region_obligations(); | |
f2b60f7d | 129 | debug!(?region_obligations); |
8faf50e0 | 130 | let region_constraints = self.with_region_constraints(|region_constraints| { |
dc9dc135 | 131 | make_query_region_constraints( |
b7449926 | 132 | tcx, |
f2b60f7d FG |
133 | region_obligations |
134 | .iter() | |
135 | .map(|r_o| (r_o.sup_type, r_o.sub_region, r_o.origin.to_constraint_category())), | |
0bf4aa26 XL |
136 | region_constraints, |
137 | ) | |
8faf50e0 | 138 | }); |
f2b60f7d | 139 | debug!(?region_constraints); |
8faf50e0 | 140 | |
dfeec247 XL |
141 | let certainty = |
142 | if ambig_errors.is_empty() { Certainty::Proven } else { Certainty::Ambiguous }; | |
8faf50e0 | 143 | |
5e7ed085 FG |
144 | let opaque_types = self.take_opaque_types_for_query_response(); |
145 | ||
0bf4aa26 | 146 | Ok(QueryResponse { |
8faf50e0 XL |
147 | var_values: inference_vars, |
148 | region_constraints, | |
149 | certainty, | |
150 | value: answer, | |
5e7ed085 | 151 | opaque_types, |
8faf50e0 XL |
152 | }) |
153 | } | |
154 | ||
5e7ed085 FG |
155 | fn take_opaque_types_for_query_response(&self) -> Vec<(Ty<'tcx>, Ty<'tcx>)> { |
156 | self.inner | |
157 | .borrow_mut() | |
158 | .opaque_type_storage | |
159 | .take_opaque_types() | |
160 | .into_iter() | |
064997fb | 161 | .map(|(k, v)| (self.tcx.mk_opaque(k.def_id.to_def_id(), k.substs), v.hidden_type.ty)) |
5e7ed085 FG |
162 | .collect() |
163 | } | |
164 | ||
8faf50e0 XL |
165 | /// Given the (canonicalized) result to a canonical query, |
166 | /// instantiates the result so it can be used, plugging in the | |
167 | /// values from the canonical query. (Note that the result may | |
168 | /// have been ambiguous; you should check the certainty level of | |
169 | /// the query before applying this function.) | |
170 | /// | |
171 | /// To get a good understanding of what is happening here, check | |
ba9703b0 | 172 | /// out the [chapter in the rustc dev guide][c]. |
8faf50e0 | 173 | /// |
f9f354fc | 174 | /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#processing-the-canonicalized-query-result |
0bf4aa26 | 175 | pub fn instantiate_query_response_and_region_obligations<R>( |
8faf50e0 XL |
176 | &self, |
177 | cause: &ObligationCause<'tcx>, | |
178 | param_env: ty::ParamEnv<'tcx>, | |
0bf4aa26 XL |
179 | original_values: &OriginalQueryValues<'tcx>, |
180 | query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, | |
8faf50e0 XL |
181 | ) -> InferResult<'tcx, R> |
182 | where | |
183 | R: Debug + TypeFoldable<'tcx>, | |
184 | { | |
dfeec247 XL |
185 | let InferOk { value: result_subst, mut obligations } = |
186 | self.query_response_substitution(cause, param_env, original_values, query_response)?; | |
8faf50e0 | 187 | |
dc9dc135 | 188 | obligations.extend(self.query_outlives_constraints_into_obligations( |
8faf50e0 XL |
189 | cause, |
190 | param_env, | |
dc9dc135 | 191 | &query_response.value.region_constraints.outlives, |
8faf50e0 XL |
192 | &result_subst, |
193 | )); | |
194 | ||
195 | let user_result: R = | |
fc512014 | 196 | query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone()); |
8faf50e0 | 197 | |
dfeec247 | 198 | Ok(InferOk { value: user_result, obligations }) |
8faf50e0 XL |
199 | } |
200 | ||
201 | /// An alternative to | |
0bf4aa26 | 202 | /// `instantiate_query_response_and_region_obligations` that is more |
8faf50e0 XL |
203 | /// efficient for NLL. NLL is a bit more advanced in the |
204 | /// "transition to chalk" than the rest of the compiler. During | |
205 | /// the NLL type check, all of the "processing" of types and | |
206 | /// things happens in queries -- the NLL checker itself is only | |
207 | /// interested in the region obligations (`'a: 'b` or `T: 'b`) | |
208 | /// that come out of these queries, which it wants to convert into | |
209 | /// MIR-based constraints and solve. Therefore, it is most | |
210 | /// convenient for the NLL Type Checker to **directly consume** | |
dc9dc135 | 211 | /// the `QueryOutlivesConstraint` values that arise from doing a |
8faf50e0 | 212 | /// query. This is contrast to other parts of the compiler, which |
dc9dc135 | 213 | /// would prefer for those `QueryOutlivesConstraint` to be converted |
8faf50e0 XL |
214 | /// into the older infcx-style constraints (e.g., calls to |
215 | /// `sub_regions` or `register_region_obligation`). | |
216 | /// | |
0bf4aa26 XL |
217 | /// Therefore, `instantiate_nll_query_response_and_region_obligations` performs the same |
218 | /// basic operations as `instantiate_query_response_and_region_obligations` but | |
8faf50e0 XL |
219 | /// it returns its result differently: |
220 | /// | |
221 | /// - It creates a substitution `S` that maps from the original | |
222 | /// query variables to the values computed in the query | |
223 | /// result. If any errors arise, they are propagated back as an | |
224 | /// `Err` result. | |
225 | /// - In the case of a successful substitution, we will append | |
dc9dc135 | 226 | /// `QueryOutlivesConstraint` values onto the |
8faf50e0 XL |
227 | /// `output_query_region_constraints` vector for the solver to |
228 | /// use (if an error arises, some values may also be pushed, but | |
229 | /// they should be ignored). | |
230 | /// - It **can happen** (though it rarely does currently) that | |
231 | /// equating types and things will give rise to subobligations | |
9fa01778 | 232 | /// that must be processed. In this case, those subobligations |
8faf50e0 XL |
233 | /// are propagated back in the return value. |
234 | /// - Finally, the query result (of type `R`) is propagated back, | |
235 | /// after applying the substitution `S`. | |
0bf4aa26 | 236 | pub fn instantiate_nll_query_response_and_region_obligations<R>( |
8faf50e0 XL |
237 | &self, |
238 | cause: &ObligationCause<'tcx>, | |
239 | param_env: ty::ParamEnv<'tcx>, | |
0bf4aa26 XL |
240 | original_values: &OriginalQueryValues<'tcx>, |
241 | query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, | |
dc9dc135 | 242 | output_query_region_constraints: &mut QueryRegionConstraints<'tcx>, |
8faf50e0 XL |
243 | ) -> InferResult<'tcx, R> |
244 | where | |
245 | R: Debug + TypeFoldable<'tcx>, | |
246 | { | |
5e7ed085 FG |
247 | let InferOk { value: result_subst, mut obligations } = self |
248 | .query_response_substitution_guess(cause, param_env, original_values, query_response)?; | |
8faf50e0 | 249 | |
dc9dc135 | 250 | // Compute `QueryOutlivesConstraint` values that unify each of |
8faf50e0 XL |
251 | // the original values `v_o` that was canonicalized into a |
252 | // variable... | |
8faf50e0 | 253 | |
f2b60f7d FG |
254 | let constraint_category = cause.to_constraint_category(); |
255 | ||
0bf4aa26 | 256 | for (index, original_value) in original_values.var_values.iter().enumerate() { |
8faf50e0 | 257 | // ...with the value `v_r` of that variable from the query. |
0bf4aa26 | 258 | let result_value = query_response.substitute_projected(self.tcx, &result_subst, |v| { |
fc512014 | 259 | v.var_values[BoundVar::new(index)] |
8faf50e0 XL |
260 | }); |
261 | match (original_value.unpack(), result_value.unpack()) { | |
5099ac24 FG |
262 | (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2)) |
263 | if re1.is_erased() && re2.is_erased() => | |
264 | { | |
e74abb32 | 265 | // No action needed. |
8faf50e0 XL |
266 | } |
267 | ||
e74abb32 | 268 | (GenericArgKind::Lifetime(v_o), GenericArgKind::Lifetime(v_r)) => { |
8faf50e0 XL |
269 | // To make `v_o = v_r`, we emit `v_o: v_r` and `v_r: v_o`. |
270 | if v_o != v_r { | |
f2b60f7d FG |
271 | output_query_region_constraints.outlives.push(( |
272 | ty::Binder::dummy(ty::OutlivesPredicate(v_o.into(), v_r)), | |
273 | constraint_category, | |
274 | )); | |
275 | output_query_region_constraints.outlives.push(( | |
276 | ty::Binder::dummy(ty::OutlivesPredicate(v_r.into(), v_o)), | |
277 | constraint_category, | |
278 | )); | |
8faf50e0 XL |
279 | } |
280 | } | |
281 | ||
e74abb32 | 282 | (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => { |
74b04a01 XL |
283 | TypeRelating::new( |
284 | self, | |
285 | QueryTypeRelatingDelegate { | |
286 | infcx: self, | |
287 | param_env, | |
288 | cause, | |
289 | obligations: &mut obligations, | |
290 | }, | |
291 | ty::Variance::Invariant, | |
292 | ) | |
f035d41b | 293 | .relate(v1, v2)?; |
8faf50e0 XL |
294 | } |
295 | ||
e74abb32 | 296 | (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => { |
74b04a01 XL |
297 | TypeRelating::new( |
298 | self, | |
299 | QueryTypeRelatingDelegate { | |
300 | infcx: self, | |
301 | param_env, | |
302 | cause, | |
303 | obligations: &mut obligations, | |
304 | }, | |
305 | ty::Variance::Invariant, | |
306 | ) | |
f035d41b | 307 | .relate(v1, v2)?; |
532ac7d7 XL |
308 | } |
309 | ||
8faf50e0 | 310 | _ => { |
dfeec247 | 311 | bug!("kind mismatch, cannot unify {:?} and {:?}", original_value, result_value); |
8faf50e0 XL |
312 | } |
313 | } | |
314 | } | |
315 | ||
316 | // ...also include the other query region constraints from the query. | |
dc9dc135 | 317 | output_query_region_constraints.outlives.extend( |
fc512014 | 318 | query_response.value.region_constraints.outlives.iter().filter_map(|&r_c| { |
a1dfa0c6 XL |
319 | let r_c = substitute_value(self.tcx, &result_subst, r_c); |
320 | ||
321 | // Screen out `'a: 'a` cases -- we skip the binder here but | |
dc9dc135 | 322 | // only compare the inner values to one another, so they are still at |
a1dfa0c6 | 323 | // consistent binding levels. |
f2b60f7d | 324 | let ty::OutlivesPredicate(k1, r2) = r_c.0.skip_binder(); |
dfeec247 XL |
325 | if k1 != r2.into() { Some(r_c) } else { None } |
326 | }), | |
0bf4aa26 | 327 | ); |
8faf50e0 | 328 | |
dc9dc135 XL |
329 | // ...also include the query member constraints. |
330 | output_query_region_constraints.member_constraints.extend( | |
dfeec247 XL |
331 | query_response |
332 | .value | |
333 | .region_constraints | |
334 | .member_constraints | |
335 | .iter() | |
fc512014 | 336 | .map(|p_c| substitute_value(self.tcx, &result_subst, p_c.clone())), |
dc9dc135 XL |
337 | ); |
338 | ||
8faf50e0 | 339 | let user_result: R = |
fc512014 | 340 | query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone()); |
8faf50e0 | 341 | |
dfeec247 | 342 | Ok(InferOk { value: user_result, obligations }) |
8faf50e0 XL |
343 | } |
344 | ||
345 | /// Given the original values and the (canonicalized) result from | |
346 | /// computing a query, returns a substitution that can be applied | |
347 | /// to the query result to convert the result back into the | |
348 | /// original namespace. | |
349 | /// | |
350 | /// The substitution also comes accompanied with subobligations | |
351 | /// that arose from unification; these might occur if (for | |
352 | /// example) we are doing lazy normalization and the value | |
353 | /// assigned to a type variable is unified with an unnormalized | |
354 | /// projection. | |
0bf4aa26 | 355 | fn query_response_substitution<R>( |
8faf50e0 XL |
356 | &self, |
357 | cause: &ObligationCause<'tcx>, | |
358 | param_env: ty::ParamEnv<'tcx>, | |
0bf4aa26 XL |
359 | original_values: &OriginalQueryValues<'tcx>, |
360 | query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, | |
8faf50e0 XL |
361 | ) -> InferResult<'tcx, CanonicalVarValues<'tcx>> |
362 | where | |
363 | R: Debug + TypeFoldable<'tcx>, | |
364 | { | |
365 | debug!( | |
0bf4aa26 XL |
366 | "query_response_substitution(original_values={:#?}, query_response={:#?})", |
367 | original_values, query_response, | |
8faf50e0 XL |
368 | ); |
369 | ||
5e7ed085 FG |
370 | let mut value = self.query_response_substitution_guess( |
371 | cause, | |
372 | param_env, | |
373 | original_values, | |
374 | query_response, | |
375 | )?; | |
8faf50e0 | 376 | |
5e7ed085 FG |
377 | value.obligations.extend( |
378 | self.unify_query_response_substitution_guess( | |
dfeec247 XL |
379 | cause, |
380 | param_env, | |
381 | original_values, | |
5e7ed085 | 382 | &value.value, |
dfeec247 XL |
383 | query_response, |
384 | )? | |
5e7ed085 FG |
385 | .into_obligations(), |
386 | ); | |
8faf50e0 | 387 | |
5e7ed085 | 388 | Ok(value) |
8faf50e0 XL |
389 | } |
390 | ||
391 | /// Given the original values and the (canonicalized) result from | |
392 | /// computing a query, returns a **guess** at a substitution that | |
393 | /// can be applied to the query result to convert the result back | |
394 | /// into the original namespace. This is called a **guess** | |
395 | /// because it uses a quick heuristic to find the values for each | |
396 | /// canonical variable; if that quick heuristic fails, then we | |
397 | /// will instantiate fresh inference variables for each canonical | |
398 | /// variable instead. Therefore, the result of this method must be | |
399 | /// properly unified | |
0bf4aa26 | 400 | fn query_response_substitution_guess<R>( |
8faf50e0 XL |
401 | &self, |
402 | cause: &ObligationCause<'tcx>, | |
5e7ed085 | 403 | param_env: ty::ParamEnv<'tcx>, |
0bf4aa26 XL |
404 | original_values: &OriginalQueryValues<'tcx>, |
405 | query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, | |
5e7ed085 | 406 | ) -> InferResult<'tcx, CanonicalVarValues<'tcx>> |
8faf50e0 XL |
407 | where |
408 | R: Debug + TypeFoldable<'tcx>, | |
409 | { | |
410 | debug!( | |
0bf4aa26 XL |
411 | "query_response_substitution_guess(original_values={:#?}, query_response={:#?})", |
412 | original_values, query_response, | |
8faf50e0 XL |
413 | ); |
414 | ||
a1dfa0c6 XL |
415 | // For each new universe created in the query result that did |
416 | // not appear in the original query, create a local | |
417 | // superuniverse. | |
418 | let mut universe_map = original_values.universe_map.clone(); | |
419 | let num_universes_in_query = original_values.universe_map.len(); | |
420 | let num_universes_in_response = query_response.max_universe.as_usize() + 1; | |
421 | for _ in num_universes_in_query..num_universes_in_response { | |
422 | universe_map.push(self.create_next_universe()); | |
423 | } | |
74b04a01 | 424 | assert!(!universe_map.is_empty()); // always have the root universe |
dfeec247 | 425 | assert_eq!(universe_map[ty::UniverseIndex::ROOT.as_usize()], ty::UniverseIndex::ROOT); |
a1dfa0c6 | 426 | |
8faf50e0 XL |
427 | // Every canonical query result includes values for each of |
428 | // the inputs to the query. Therefore, we begin by unifying | |
429 | // these values with the original inputs that were | |
430 | // canonicalized. | |
0bf4aa26 XL |
431 | let result_values = &query_response.value.var_values; |
432 | assert_eq!(original_values.var_values.len(), result_values.len()); | |
8faf50e0 XL |
433 | |
434 | // Quickly try to find initial values for the canonical | |
435 | // variables in the result in terms of the query. We do this | |
436 | // by iterating down the values that the query gave to each of | |
437 | // the canonical inputs. If we find that one of those values | |
438 | // is directly equal to one of the canonical variables in the | |
439 | // result, then we can type the corresponding value from the | |
440 | // input. See the example above. | |
e74abb32 | 441 | let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'tcx>>> = |
0bf4aa26 | 442 | IndexVec::from_elem_n(None, query_response.variables.len()); |
8faf50e0 XL |
443 | |
444 | // In terms of our example above, we are iterating over pairs like: | |
445 | // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)] | |
cdc7bbd5 XL |
446 | for (original_value, result_value) in iter::zip(&original_values.var_values, result_values) |
447 | { | |
8faf50e0 | 448 | match result_value.unpack() { |
e74abb32 | 449 | GenericArgKind::Type(result_value) => { |
8faf50e0 | 450 | // e.g., here `result_value` might be `?0` in the example above... |
1b1a35ee | 451 | if let ty::Bound(debruijn, b) = *result_value.kind() { |
a1dfa0c6 XL |
452 | // ...in which case we would set `canonical_vars[0]` to `Some(?U)`. |
453 | ||
454 | // We only allow a `ty::INNERMOST` index in substitutions. | |
455 | assert_eq!(debruijn, ty::INNERMOST); | |
0bf4aa26 | 456 | opt_values[b.var] = Some(*original_value); |
8faf50e0 XL |
457 | } |
458 | } | |
e74abb32 | 459 | GenericArgKind::Lifetime(result_value) => { |
8faf50e0 | 460 | // e.g., here `result_value` might be `'?1` in the example above... |
5099ac24 | 461 | if let ty::ReLateBound(debruijn, br) = *result_value { |
a1dfa0c6 XL |
462 | // ... in which case we would set `canonical_vars[0]` to `Some('static)`. |
463 | ||
464 | // We only allow a `ty::INNERMOST` index in substitutions. | |
465 | assert_eq!(debruijn, ty::INNERMOST); | |
cdc7bbd5 | 466 | opt_values[br.var] = Some(*original_value); |
8faf50e0 XL |
467 | } |
468 | } | |
e74abb32 | 469 | GenericArgKind::Const(result_value) => { |
923072b8 | 470 | if let ty::ConstKind::Bound(debrujin, b) = result_value.kind() { |
48663c56 XL |
471 | // ...in which case we would set `canonical_vars[0]` to `Some(const X)`. |
472 | ||
473 | // We only allow a `ty::INNERMOST` index in substitutions. | |
5099ac24 FG |
474 | assert_eq!(debrujin, ty::INNERMOST); |
475 | opt_values[b] = Some(*original_value); | |
48663c56 | 476 | } |
532ac7d7 | 477 | } |
8faf50e0 XL |
478 | } |
479 | } | |
480 | ||
481 | // Create a result substitution: if we found a value for a | |
482 | // given variable in the loop above, use that. Otherwise, use | |
483 | // a fresh inference variable. | |
484 | let result_subst = CanonicalVarValues { | |
0bf4aa26 | 485 | var_values: query_response |
8faf50e0 XL |
486 | .variables |
487 | .iter() | |
488 | .enumerate() | |
a1dfa0c6 XL |
489 | .map(|(index, info)| { |
490 | if info.is_existential() { | |
491 | match opt_values[BoundVar::new(index)] { | |
492 | Some(k) => k, | |
f9f354fc | 493 | None => self.instantiate_canonical_var(cause.span, info, |u| { |
a1dfa0c6 XL |
494 | universe_map[u.as_usize()] |
495 | }), | |
496 | } | |
497 | } else { | |
f9f354fc | 498 | self.instantiate_canonical_var(cause.span, info, |u| { |
a1dfa0c6 XL |
499 | universe_map[u.as_usize()] |
500 | }) | |
501 | } | |
502 | }) | |
8faf50e0 XL |
503 | .collect(), |
504 | }; | |
505 | ||
5e7ed085 FG |
506 | let mut obligations = vec![]; |
507 | ||
508 | // Carry all newly resolved opaque types to the caller's scope | |
509 | for &(a, b) in &query_response.value.opaque_types { | |
510 | let a = substitute_value(self.tcx, &result_subst, a); | |
511 | let b = substitute_value(self.tcx, &result_subst, b); | |
2b03887a | 512 | obligations.extend(self.at(cause, param_env).eq(a, b)?.obligations); |
5e7ed085 FG |
513 | } |
514 | ||
515 | Ok(InferOk { value: result_subst, obligations }) | |
8faf50e0 XL |
516 | } |
517 | ||
518 | /// Given a "guess" at the values for the canonical variables in | |
519 | /// the input, try to unify with the *actual* values found in the | |
9fa01778 | 520 | /// query result. Often, but not always, this is a no-op, because |
8faf50e0 XL |
521 | /// we already found the mapping in the "guessing" step. |
522 | /// | |
0bf4aa26 XL |
523 | /// See also: `query_response_substitution_guess` |
524 | fn unify_query_response_substitution_guess<R>( | |
8faf50e0 XL |
525 | &self, |
526 | cause: &ObligationCause<'tcx>, | |
527 | param_env: ty::ParamEnv<'tcx>, | |
0bf4aa26 | 528 | original_values: &OriginalQueryValues<'tcx>, |
8faf50e0 | 529 | result_subst: &CanonicalVarValues<'tcx>, |
0bf4aa26 | 530 | query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, |
8faf50e0 XL |
531 | ) -> InferResult<'tcx, ()> |
532 | where | |
533 | R: Debug + TypeFoldable<'tcx>, | |
534 | { | |
535 | // A closure that yields the result value for the given | |
536 | // canonical variable; this is taken from | |
0bf4aa26 | 537 | // `query_response.var_values` after applying the substitution |
8faf50e0 | 538 | // `result_subst`. |
e74abb32 | 539 | let substituted_query_response = |index: BoundVar| -> GenericArg<'tcx> { |
fc512014 | 540 | query_response.substitute_projected(self.tcx, &result_subst, |v| v.var_values[index]) |
8faf50e0 XL |
541 | }; |
542 | ||
543 | // Unify the original value for each variable with the value | |
0bf4aa26 | 544 | // taken from `query_response` (after applying `result_subst`). |
6a06907d | 545 | self.unify_canonical_vars(cause, param_env, original_values, substituted_query_response) |
8faf50e0 XL |
546 | } |
547 | ||
548 | /// Converts the region constraints resulting from a query into an | |
549 | /// iterator of obligations. | |
dc9dc135 | 550 | fn query_outlives_constraints_into_obligations<'a>( |
8faf50e0 XL |
551 | &'a self, |
552 | cause: &'a ObligationCause<'tcx>, | |
553 | param_env: ty::ParamEnv<'tcx>, | |
dc9dc135 | 554 | unsubstituted_region_constraints: &'a [QueryOutlivesConstraint<'tcx>], |
8faf50e0 | 555 | result_subst: &'a CanonicalVarValues<'tcx>, |
dc9dc135 | 556 | ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a + Captures<'tcx> { |
fc512014 XL |
557 | unsubstituted_region_constraints.iter().map(move |&constraint| { |
558 | let predicate = substitute_value(self.tcx, result_subst, constraint); | |
923072b8 FG |
559 | self.query_outlives_constraint_to_obligation(predicate, cause.clone(), param_env) |
560 | }) | |
561 | } | |
dfeec247 | 562 | |
923072b8 FG |
563 | pub fn query_outlives_constraint_to_obligation( |
564 | &self, | |
565 | predicate: QueryOutlivesConstraint<'tcx>, | |
566 | cause: ObligationCause<'tcx>, | |
567 | param_env: ty::ParamEnv<'tcx>, | |
568 | ) -> Obligation<'tcx, ty::Predicate<'tcx>> { | |
f2b60f7d | 569 | let ty::OutlivesPredicate(k1, r2) = predicate.0.skip_binder(); |
3dfed10e | 570 | |
923072b8 FG |
571 | let atom = match k1.unpack() { |
572 | GenericArgKind::Lifetime(r1) => { | |
573 | ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r1, r2)) | |
574 | } | |
575 | GenericArgKind::Type(t1) => { | |
576 | ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(t1, r2)) | |
577 | } | |
578 | GenericArgKind::Const(..) => { | |
579 | // Consts cannot outlive one another, so we don't expect to | |
580 | // encounter this branch. | |
581 | span_bug!(cause.span, "unexpected const outlives {:?}", predicate); | |
582 | } | |
583 | }; | |
f2b60f7d | 584 | let predicate = predicate.0.rebind(atom).to_predicate(self.tcx); |
923072b8 FG |
585 | |
586 | Obligation::new(cause, param_env, predicate) | |
8faf50e0 XL |
587 | } |
588 | ||
589 | /// Given two sets of values for the same set of canonical variables, unify them. | |
a1dfa0c6 | 590 | /// The second set is produced lazily by supplying indices from the first set. |
8faf50e0 XL |
591 | fn unify_canonical_vars( |
592 | &self, | |
593 | cause: &ObligationCause<'tcx>, | |
594 | param_env: ty::ParamEnv<'tcx>, | |
0bf4aa26 | 595 | variables1: &OriginalQueryValues<'tcx>, |
e74abb32 | 596 | variables2: impl Fn(BoundVar) -> GenericArg<'tcx>, |
8faf50e0 XL |
597 | ) -> InferResult<'tcx, ()> { |
598 | self.commit_if_ok(|_| { | |
599 | let mut obligations = vec![]; | |
0bf4aa26 | 600 | for (index, value1) in variables1.var_values.iter().enumerate() { |
a1dfa0c6 | 601 | let value2 = variables2(BoundVar::new(index)); |
8faf50e0 XL |
602 | |
603 | match (value1.unpack(), value2.unpack()) { | |
e74abb32 | 604 | (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => { |
8faf50e0 XL |
605 | obligations |
606 | .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); | |
607 | } | |
5099ac24 FG |
608 | (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2)) |
609 | if re1.is_erased() && re2.is_erased() => | |
610 | { | |
8faf50e0 XL |
611 | // no action needed |
612 | } | |
e74abb32 | 613 | (GenericArgKind::Lifetime(v1), GenericArgKind::Lifetime(v2)) => { |
8faf50e0 XL |
614 | obligations |
615 | .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); | |
616 | } | |
e74abb32 | 617 | (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => { |
48663c56 XL |
618 | let ok = self.at(cause, param_env).eq(v1, v2)?; |
619 | obligations.extend(ok.into_obligations()); | |
532ac7d7 | 620 | } |
8faf50e0 XL |
621 | _ => { |
622 | bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,); | |
623 | } | |
624 | } | |
625 | } | |
dfeec247 | 626 | Ok(InferOk { value: (), obligations }) |
8faf50e0 XL |
627 | }) |
628 | } | |
629 | } | |
630 | ||
631 | /// Given the region obligations and constraints scraped from the infcx, | |
632 | /// creates query region constraints. | |
dc9dc135 XL |
633 | pub fn make_query_region_constraints<'tcx>( |
634 | tcx: TyCtxt<'tcx>, | |
f2b60f7d | 635 | outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>, ConstraintCategory<'tcx>)>, |
8faf50e0 | 636 | region_constraints: &RegionConstraintData<'tcx>, |
dc9dc135 | 637 | ) -> QueryRegionConstraints<'tcx> { |
dfeec247 XL |
638 | let RegionConstraintData { constraints, verifys, givens, member_constraints } = |
639 | region_constraints; | |
8faf50e0 XL |
640 | |
641 | assert!(verifys.is_empty()); | |
642 | assert!(givens.is_empty()); | |
643 | ||
f2b60f7d FG |
644 | debug!(?constraints); |
645 | ||
0bf4aa26 | 646 | let outlives: Vec<_> = constraints |
74b04a01 | 647 | .iter() |
f2b60f7d FG |
648 | .map(|(k, origin)| { |
649 | // no bound vars in the code above | |
650 | let constraint = ty::Binder::dummy(match *k { | |
651 | // Swap regions because we are going from sub (<=) to outlives | |
652 | // (>=). | |
653 | Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate( | |
654 | tcx.mk_region(ty::ReVar(v2)).into(), | |
655 | tcx.mk_region(ty::ReVar(v1)), | |
656 | ), | |
657 | Constraint::VarSubReg(v1, r2) => { | |
658 | ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1))) | |
659 | } | |
660 | Constraint::RegSubVar(r1, v2) => { | |
661 | ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1) | |
662 | } | |
663 | Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1), | |
664 | }); | |
665 | (constraint, origin.to_constraint_category()) | |
0bf4aa26 | 666 | }) |
0bf4aa26 XL |
667 | .chain( |
668 | outlives_obligations | |
f2b60f7d FG |
669 | // no bound vars in the code above |
670 | .map(|(ty, r, constraint_category)| { | |
671 | (ty::Binder::dummy(ty::OutlivesPredicate(ty.into(), r)), constraint_category) | |
672 | }), | |
0bf4aa26 XL |
673 | ) |
674 | .collect(); | |
8faf50e0 | 675 | |
dc9dc135 | 676 | QueryRegionConstraints { outlives, member_constraints: member_constraints.clone() } |
8faf50e0 | 677 | } |
74b04a01 XL |
678 | |
679 | struct QueryTypeRelatingDelegate<'a, 'tcx> { | |
2b03887a | 680 | infcx: &'a InferCtxt<'tcx>, |
74b04a01 XL |
681 | obligations: &'a mut Vec<PredicateObligation<'tcx>>, |
682 | param_env: ty::ParamEnv<'tcx>, | |
683 | cause: &'a ObligationCause<'tcx>, | |
684 | } | |
685 | ||
686 | impl<'tcx> TypeRelatingDelegate<'tcx> for QueryTypeRelatingDelegate<'_, 'tcx> { | |
5e7ed085 FG |
687 | fn span(&self) -> Span { |
688 | self.cause.span | |
689 | } | |
690 | ||
6a06907d XL |
691 | fn param_env(&self) -> ty::ParamEnv<'tcx> { |
692 | self.param_env | |
693 | } | |
694 | ||
74b04a01 XL |
695 | fn create_next_universe(&mut self) -> ty::UniverseIndex { |
696 | self.infcx.create_next_universe() | |
697 | } | |
698 | ||
699 | fn next_existential_region_var(&mut self, from_forall: bool) -> ty::Region<'tcx> { | |
5869c6ff | 700 | let origin = NllRegionVariableOrigin::Existential { from_forall }; |
74b04a01 XL |
701 | self.infcx.next_nll_region_var(origin) |
702 | } | |
703 | ||
704 | fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> { | |
705 | self.infcx.tcx.mk_region(ty::RePlaceholder(placeholder)) | |
706 | } | |
707 | ||
708 | fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> { | |
709 | self.infcx.next_nll_region_var_in_universe( | |
5869c6ff | 710 | NllRegionVariableOrigin::Existential { from_forall: false }, |
74b04a01 XL |
711 | universe, |
712 | ) | |
713 | } | |
714 | ||
17df50a5 XL |
715 | fn push_outlives( |
716 | &mut self, | |
717 | sup: ty::Region<'tcx>, | |
718 | sub: ty::Region<'tcx>, | |
719 | _info: ty::VarianceDiagInfo<'tcx>, | |
720 | ) { | |
74b04a01 XL |
721 | self.obligations.push(Obligation { |
722 | cause: self.cause.clone(), | |
723 | param_env: self.param_env, | |
c295e0f8 XL |
724 | predicate: ty::Binder::dummy(ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate( |
725 | sup, sub, | |
726 | ))) | |
727 | .to_predicate(self.infcx.tcx), | |
74b04a01 XL |
728 | recursion_depth: 0, |
729 | }); | |
730 | } | |
731 | ||
5099ac24 | 732 | fn const_equate(&mut self, _a: Const<'tcx>, _b: Const<'tcx>) { |
064997fb | 733 | span_bug!(self.cause.span(), "generic_const_exprs: unreachable `const_equate`"); |
74b04a01 XL |
734 | } |
735 | ||
736 | fn normalization() -> NormalizationStrategy { | |
737 | NormalizationStrategy::Eager | |
738 | } | |
739 | ||
740 | fn forbid_inference_vars() -> bool { | |
741 | true | |
742 | } | |
5e7ed085 | 743 | |
2b03887a | 744 | fn register_opaque_type_obligations( |
5e7ed085 | 745 | &mut self, |
2b03887a | 746 | obligations: PredicateObligations<'tcx>, |
5e7ed085 | 747 | ) -> Result<(), TypeError<'tcx>> { |
2b03887a | 748 | self.obligations.extend(obligations); |
5e7ed085 FG |
749 | Ok(()) |
750 | } | |
74b04a01 | 751 | } |