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