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.
5 //! For an overview of what canonicaliation is and how it fits into
6 //! rustc, check out the [chapter in the rustc dev guide][c].
8 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
10 use crate::infer::canonical::substitute::{substitute_value, CanonicalExt};
11 use crate::infer::canonical::{
12 Canonical, CanonicalVarValues, CanonicalizedQueryResponse, Certainty, OriginalQueryValues,
13 QueryOutlivesConstraint, QueryRegionConstraints, QueryResponse,
15 use crate::infer::nll_relate::{NormalizationStrategy, TypeRelating, TypeRelatingDelegate};
16 use crate::infer::region_constraints::{Constraint, RegionConstraintData};
17 use crate::infer::{InferCtxt, InferOk, InferResult, NllRegionVariableOrigin};
18 use crate::traits::query::{Fallible, NoSolution};
19 use crate::traits::TraitEngine;
20 use crate::traits::{Obligation, ObligationCause, PredicateObligation};
21 use rustc_data_structures::captures::Captures;
22 use rustc_index::vec::Idx;
23 use rustc_index::vec::IndexVec;
24 use rustc_middle::arena::ArenaAllocatable;
25 use rustc_middle::ty::fold::TypeFoldable;
26 use rustc_middle::ty::relate::TypeRelation;
27 use rustc_middle::ty::subst::{GenericArg, GenericArgKind};
28 use rustc_middle::ty::{self, BoundVar, Const, ToPredicate, Ty, TyCtxt};
31 impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
32 /// This method is meant to be invoked as the final step of a canonical query
33 /// implementation. It is given:
35 /// - the instantiated variables `inference_vars` created from the query key
36 /// - the result `answer` of the query
37 /// - a fulfillment context `fulfill_cx` that may contain various obligations which
38 /// have yet to be proven.
40 /// Given this, the function will process the obligations pending
43 /// - If all the obligations can be proven successfully, it will
44 /// package up any resulting region obligations (extracted from
45 /// `infcx`) along with the fully resolved value `answer` into a
46 /// query result (which is then itself canonicalized).
47 /// - If some obligations can be neither proven nor disproven, then
48 /// the same thing happens, but the resulting query is marked as ambiguous.
49 /// - Finally, if any of the obligations result in a hard error,
50 /// then `Err(NoSolution)` is returned.
51 pub fn make_canonicalized_query_response<T>(
53 inference_vars: CanonicalVarValues<'tcx>,
55 fulfill_cx: &mut dyn TraitEngine<'tcx>,
56 ) -> Fallible<CanonicalizedQueryResponse<'tcx, T>>
58 T: Debug + TypeFoldable<'tcx>,
59 Canonical<'tcx, QueryResponse<'tcx, T>>: ArenaAllocatable<'tcx>,
61 let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?;
62 let canonical_result = self.canonicalize_response(query_response);
64 debug!("make_canonicalized_query_response: canonical_result = {:#?}", canonical_result);
66 Ok(self.tcx.arena.alloc(canonical_result))
69 /// A version of `make_canonicalized_query_response` that does
70 /// not pack in obligations, for contexts that want to drop
71 /// pending obligations instead of treating them as an ambiguity (e.g.
72 /// typeck "probing" contexts).
74 /// If you DO want to keep track of pending obligations (which
75 /// include all region obligations, so this includes all cases
76 /// that care about regions) with this function, you have to
77 /// do it yourself, by e.g., having them be a part of the answer.
78 pub fn make_query_response_ignoring_pending_obligations<T>(
80 inference_vars: CanonicalVarValues<'tcx>,
82 ) -> Canonical<'tcx, QueryResponse<'tcx, T>>
84 T: Debug + TypeFoldable<'tcx>,
86 self.canonicalize_response(QueryResponse {
87 var_values: inference_vars,
88 region_constraints: QueryRegionConstraints::default(),
89 certainty: Certainty::Proven, // Ambiguities are OK!
94 /// Helper for `make_canonicalized_query_response` that does
95 /// everything up until the final canonicalization.
96 fn make_query_response<T>(
98 inference_vars: CanonicalVarValues<'tcx>,
100 fulfill_cx: &mut dyn TraitEngine<'tcx>,
101 ) -> Result<QueryResponse<'tcx, T>, NoSolution>
103 T: Debug + TypeFoldable<'tcx>,
108 "make_query_response(\
109 inference_vars={:?}, \
111 inference_vars, answer,
114 // Select everything, returning errors.
115 let true_errors = fulfill_cx.select_where_possible(self).err().unwrap_or_else(Vec::new);
116 debug!("true_errors = {:#?}", true_errors);
118 if !true_errors.is_empty() {
119 // FIXME -- we don't indicate *why* we failed to solve
120 debug!("make_query_response: true_errors={:#?}", true_errors);
121 return Err(NoSolution);
124 // Anything left unselected *now* must be an ambiguity.
125 let ambig_errors = fulfill_cx.select_all_or_error(self).err().unwrap_or_else(Vec::new);
126 debug!("ambig_errors = {:#?}", ambig_errors);
128 let region_obligations = self.take_registered_region_obligations();
129 let region_constraints = self.with_region_constraints(|region_constraints| {
130 make_query_region_constraints(
132 region_obligations.iter().map(|(_, r_o)| (r_o.sup_type, r_o.sub_region)),
138 if ambig_errors.is_empty() { Certainty::Proven } else { Certainty::Ambiguous };
141 var_values: inference_vars,
148 /// Given the (canonicalized) result to a canonical query,
149 /// instantiates the result so it can be used, plugging in the
150 /// values from the canonical query. (Note that the result may
151 /// have been ambiguous; you should check the certainty level of
152 /// the query before applying this function.)
154 /// To get a good understanding of what is happening here, check
155 /// out the [chapter in the rustc dev guide][c].
157 /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#processing-the-canonicalized-query-result
158 pub fn instantiate_query_response_and_region_obligations<R>(
160 cause: &ObligationCause<'tcx>,
161 param_env: ty::ParamEnv<'tcx>,
162 original_values: &OriginalQueryValues<'tcx>,
163 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
164 ) -> InferResult<'tcx, R>
166 R: Debug + TypeFoldable<'tcx>,
168 let InferOk { value: result_subst, mut obligations } =
169 self.query_response_substitution(cause, param_env, original_values, query_response)?;
171 obligations.extend(self.query_outlives_constraints_into_obligations(
174 &query_response.value.region_constraints.outlives,
179 query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone());
181 Ok(InferOk { value: user_result, obligations })
184 /// An alternative to
185 /// `instantiate_query_response_and_region_obligations` that is more
186 /// efficient for NLL. NLL is a bit more advanced in the
187 /// "transition to chalk" than the rest of the compiler. During
188 /// the NLL type check, all of the "processing" of types and
189 /// things happens in queries -- the NLL checker itself is only
190 /// interested in the region obligations (`'a: 'b` or `T: 'b`)
191 /// that come out of these queries, which it wants to convert into
192 /// MIR-based constraints and solve. Therefore, it is most
193 /// convenient for the NLL Type Checker to **directly consume**
194 /// the `QueryOutlivesConstraint` values that arise from doing a
195 /// query. This is contrast to other parts of the compiler, which
196 /// would prefer for those `QueryOutlivesConstraint` to be converted
197 /// into the older infcx-style constraints (e.g., calls to
198 /// `sub_regions` or `register_region_obligation`).
200 /// Therefore, `instantiate_nll_query_response_and_region_obligations` performs the same
201 /// basic operations as `instantiate_query_response_and_region_obligations` but
202 /// it returns its result differently:
204 /// - It creates a substitution `S` that maps from the original
205 /// query variables to the values computed in the query
206 /// result. If any errors arise, they are propagated back as an
208 /// - In the case of a successful substitution, we will append
209 /// `QueryOutlivesConstraint` values onto the
210 /// `output_query_region_constraints` vector for the solver to
211 /// use (if an error arises, some values may also be pushed, but
212 /// they should be ignored).
213 /// - It **can happen** (though it rarely does currently) that
214 /// equating types and things will give rise to subobligations
215 /// that must be processed. In this case, those subobligations
216 /// are propagated back in the return value.
217 /// - Finally, the query result (of type `R`) is propagated back,
218 /// after applying the substitution `S`.
219 pub fn instantiate_nll_query_response_and_region_obligations<R>(
221 cause: &ObligationCause<'tcx>,
222 param_env: ty::ParamEnv<'tcx>,
223 original_values: &OriginalQueryValues<'tcx>,
224 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
225 output_query_region_constraints: &mut QueryRegionConstraints<'tcx>,
226 ) -> InferResult<'tcx, R>
228 R: Debug + TypeFoldable<'tcx>,
231 self.query_response_substitution_guess(cause, original_values, query_response);
233 // Compute `QueryOutlivesConstraint` values that unify each of
234 // the original values `v_o` that was canonicalized into a
236 let mut obligations = vec![];
238 for (index, original_value) in original_values.var_values.iter().enumerate() {
239 // ...with the value `v_r` of that variable from the query.
240 let result_value = query_response.substitute_projected(self.tcx, &result_subst, |v| {
241 v.var_values[BoundVar::new(index)]
243 match (original_value.unpack(), result_value.unpack()) {
245 GenericArgKind::Lifetime(ty::ReErased),
246 GenericArgKind::Lifetime(ty::ReErased),
251 (GenericArgKind::Lifetime(v_o), GenericArgKind::Lifetime(v_r)) => {
252 // To make `v_o = v_r`, we emit `v_o: v_r` and `v_r: v_o`.
254 output_query_region_constraints
256 .push(ty::Binder::dummy(ty::OutlivesPredicate(v_o.into(), v_r)));
257 output_query_region_constraints
259 .push(ty::Binder::dummy(ty::OutlivesPredicate(v_r.into(), v_o)));
263 (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
266 QueryTypeRelatingDelegate {
270 obligations: &mut obligations,
272 ty::Variance::Invariant,
277 (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
280 QueryTypeRelatingDelegate {
284 obligations: &mut obligations,
286 ty::Variance::Invariant,
292 bug!("kind mismatch, cannot unify {:?} and {:?}", original_value, result_value);
297 // ...also include the other query region constraints from the query.
298 output_query_region_constraints.outlives.extend(
299 query_response.value.region_constraints.outlives.iter().filter_map(|&r_c| {
300 let r_c = substitute_value(self.tcx, &result_subst, r_c);
302 // Screen out `'a: 'a` cases -- we skip the binder here but
303 // only compare the inner values to one another, so they are still at
304 // consistent binding levels.
305 let ty::OutlivesPredicate(k1, r2) = r_c.skip_binder();
306 if k1 != r2.into() { Some(r_c) } else { None }
310 // ...also include the query member constraints.
311 output_query_region_constraints.member_constraints.extend(
317 .map(|p_c| substitute_value(self.tcx, &result_subst, p_c.clone())),
321 query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone());
323 Ok(InferOk { value: user_result, obligations })
326 /// Given the original values and the (canonicalized) result from
327 /// computing a query, returns a substitution that can be applied
328 /// to the query result to convert the result back into the
329 /// original namespace.
331 /// The substitution also comes accompanied with subobligations
332 /// that arose from unification; these might occur if (for
333 /// example) we are doing lazy normalization and the value
334 /// assigned to a type variable is unified with an unnormalized
336 fn query_response_substitution<R>(
338 cause: &ObligationCause<'tcx>,
339 param_env: ty::ParamEnv<'tcx>,
340 original_values: &OriginalQueryValues<'tcx>,
341 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
342 ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
344 R: Debug + TypeFoldable<'tcx>,
347 "query_response_substitution(original_values={:#?}, query_response={:#?})",
348 original_values, query_response,
352 self.query_response_substitution_guess(cause, original_values, query_response);
354 let obligations = self
355 .unify_query_response_substitution_guess(
364 Ok(InferOk { value: result_subst, obligations })
367 /// Given the original values and the (canonicalized) result from
368 /// computing a query, returns a **guess** at a substitution that
369 /// can be applied to the query result to convert the result back
370 /// into the original namespace. This is called a **guess**
371 /// because it uses a quick heuristic to find the values for each
372 /// canonical variable; if that quick heuristic fails, then we
373 /// will instantiate fresh inference variables for each canonical
374 /// variable instead. Therefore, the result of this method must be
376 fn query_response_substitution_guess<R>(
378 cause: &ObligationCause<'tcx>,
379 original_values: &OriginalQueryValues<'tcx>,
380 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
381 ) -> CanonicalVarValues<'tcx>
383 R: Debug + TypeFoldable<'tcx>,
386 "query_response_substitution_guess(original_values={:#?}, query_response={:#?})",
387 original_values, query_response,
390 // For each new universe created in the query result that did
391 // not appear in the original query, create a local
393 let mut universe_map = original_values.universe_map.clone();
394 let num_universes_in_query = original_values.universe_map.len();
395 let num_universes_in_response = query_response.max_universe.as_usize() + 1;
396 for _ in num_universes_in_query..num_universes_in_response {
397 universe_map.push(self.create_next_universe());
399 assert!(!universe_map.is_empty()); // always have the root universe
400 assert_eq!(universe_map[ty::UniverseIndex::ROOT.as_usize()], ty::UniverseIndex::ROOT);
402 // Every canonical query result includes values for each of
403 // the inputs to the query. Therefore, we begin by unifying
404 // these values with the original inputs that were
406 let result_values = &query_response.value.var_values;
407 assert_eq!(original_values.var_values.len(), result_values.len());
409 // Quickly try to find initial values for the canonical
410 // variables in the result in terms of the query. We do this
411 // by iterating down the values that the query gave to each of
412 // the canonical inputs. If we find that one of those values
413 // is directly equal to one of the canonical variables in the
414 // result, then we can type the corresponding value from the
415 // input. See the example above.
416 let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'tcx>>> =
417 IndexVec::from_elem_n(None, query_response.variables.len());
419 // In terms of our example above, we are iterating over pairs like:
420 // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)]
421 for (original_value, result_value) in original_values.var_values.iter().zip(result_values) {
422 match result_value.unpack() {
423 GenericArgKind::Type(result_value) => {
424 // e.g., here `result_value` might be `?0` in the example above...
425 if let ty::Bound(debruijn, b) = *result_value.kind() {
426 // ...in which case we would set `canonical_vars[0]` to `Some(?U)`.
428 // We only allow a `ty::INNERMOST` index in substitutions.
429 assert_eq!(debruijn, ty::INNERMOST);
430 opt_values[b.var] = Some(*original_value);
433 GenericArgKind::Lifetime(result_value) => {
434 // e.g., here `result_value` might be `'?1` in the example above...
435 if let &ty::RegionKind::ReLateBound(debruijn, br) = result_value {
436 // ... in which case we would set `canonical_vars[0]` to `Some('static)`.
438 // We only allow a `ty::INNERMOST` index in substitutions.
439 assert_eq!(debruijn, ty::INNERMOST);
440 opt_values[br.assert_bound_var()] = Some(*original_value);
443 GenericArgKind::Const(result_value) => {
444 if let ty::Const { val: ty::ConstKind::Bound(debrujin, b), .. } = result_value {
445 // ...in which case we would set `canonical_vars[0]` to `Some(const X)`.
447 // We only allow a `ty::INNERMOST` index in substitutions.
448 assert_eq!(*debrujin, ty::INNERMOST);
449 opt_values[*b] = Some(*original_value);
455 // Create a result substitution: if we found a value for a
456 // given variable in the loop above, use that. Otherwise, use
457 // a fresh inference variable.
458 let result_subst = CanonicalVarValues {
459 var_values: query_response
463 .map(|(index, info)| {
464 if info.is_existential() {
465 match opt_values[BoundVar::new(index)] {
467 None => self.instantiate_canonical_var(cause.span, info, |u| {
468 universe_map[u.as_usize()]
472 self.instantiate_canonical_var(cause.span, info, |u| {
473 universe_map[u.as_usize()]
483 /// Given a "guess" at the values for the canonical variables in
484 /// the input, try to unify with the *actual* values found in the
485 /// query result. Often, but not always, this is a no-op, because
486 /// we already found the mapping in the "guessing" step.
488 /// See also: `query_response_substitution_guess`
489 fn unify_query_response_substitution_guess<R>(
491 cause: &ObligationCause<'tcx>,
492 param_env: ty::ParamEnv<'tcx>,
493 original_values: &OriginalQueryValues<'tcx>,
494 result_subst: &CanonicalVarValues<'tcx>,
495 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
496 ) -> InferResult<'tcx, ()>
498 R: Debug + TypeFoldable<'tcx>,
500 // A closure that yields the result value for the given
501 // canonical variable; this is taken from
502 // `query_response.var_values` after applying the substitution
504 let substituted_query_response = |index: BoundVar| -> GenericArg<'tcx> {
505 query_response.substitute_projected(self.tcx, &result_subst, |v| v.var_values[index])
508 // Unify the original value for each variable with the value
509 // taken from `query_response` (after applying `result_subst`).
510 Ok(self.unify_canonical_vars(
514 substituted_query_response,
518 /// Converts the region constraints resulting from a query into an
519 /// iterator of obligations.
520 fn query_outlives_constraints_into_obligations<'a>(
522 cause: &'a ObligationCause<'tcx>,
523 param_env: ty::ParamEnv<'tcx>,
524 unsubstituted_region_constraints: &'a [QueryOutlivesConstraint<'tcx>],
525 result_subst: &'a CanonicalVarValues<'tcx>,
526 ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a + Captures<'tcx> {
527 unsubstituted_region_constraints.iter().map(move |&constraint| {
528 let predicate = substitute_value(self.tcx, result_subst, constraint);
529 let ty::OutlivesPredicate(k1, r2) = predicate.skip_binder();
531 let atom = match k1.unpack() {
532 GenericArgKind::Lifetime(r1) => {
533 ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r1, r2))
535 GenericArgKind::Type(t1) => {
536 ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(t1, r2))
538 GenericArgKind::Const(..) => {
539 // Consts cannot outlive one another, so we don't expect to
540 // encounter this branch.
541 span_bug!(cause.span, "unexpected const outlives {:?}", constraint);
544 let predicate = predicate.rebind(atom).to_predicate(self.tcx);
546 Obligation::new(cause.clone(), param_env, predicate)
550 /// Given two sets of values for the same set of canonical variables, unify them.
551 /// The second set is produced lazily by supplying indices from the first set.
552 fn unify_canonical_vars(
554 cause: &ObligationCause<'tcx>,
555 param_env: ty::ParamEnv<'tcx>,
556 variables1: &OriginalQueryValues<'tcx>,
557 variables2: impl Fn(BoundVar) -> GenericArg<'tcx>,
558 ) -> InferResult<'tcx, ()> {
559 self.commit_if_ok(|_| {
560 let mut obligations = vec![];
561 for (index, value1) in variables1.var_values.iter().enumerate() {
562 let value2 = variables2(BoundVar::new(index));
564 match (value1.unpack(), value2.unpack()) {
565 (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
567 .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
570 GenericArgKind::Lifetime(ty::ReErased),
571 GenericArgKind::Lifetime(ty::ReErased),
575 (GenericArgKind::Lifetime(v1), GenericArgKind::Lifetime(v2)) => {
577 .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
579 (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
580 let ok = self.at(cause, param_env).eq(v1, v2)?;
581 obligations.extend(ok.into_obligations());
584 bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
588 Ok(InferOk { value: (), obligations })
593 /// Given the region obligations and constraints scraped from the infcx,
594 /// creates query region constraints.
595 pub fn make_query_region_constraints<'tcx>(
597 outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>)>,
598 region_constraints: &RegionConstraintData<'tcx>,
599 ) -> QueryRegionConstraints<'tcx> {
600 let RegionConstraintData { constraints, verifys, givens, member_constraints } =
603 assert!(verifys.is_empty());
604 assert!(givens.is_empty());
606 let outlives: Vec<_> = constraints
608 .map(|(k, _)| match *k {
609 // Swap regions because we are going from sub (<=) to outlives
611 Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate(
612 tcx.mk_region(ty::ReVar(v2)).into(),
613 tcx.mk_region(ty::ReVar(v1)),
615 Constraint::VarSubReg(v1, r2) => {
616 ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1)))
618 Constraint::RegSubVar(r1, v2) => {
619 ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1)
621 Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1),
623 .map(ty::Binder::dummy) // no bound vars in the code above
626 .map(|(ty, r)| ty::OutlivesPredicate(ty.into(), r))
627 .map(ty::Binder::dummy), // no bound vars in the code above
631 QueryRegionConstraints { outlives, member_constraints: member_constraints.clone() }
634 struct QueryTypeRelatingDelegate<'a, 'tcx> {
635 infcx: &'a InferCtxt<'a, 'tcx>,
636 obligations: &'a mut Vec<PredicateObligation<'tcx>>,
637 param_env: ty::ParamEnv<'tcx>,
638 cause: &'a ObligationCause<'tcx>,
641 impl<'tcx> TypeRelatingDelegate<'tcx> for QueryTypeRelatingDelegate<'_, 'tcx> {
642 fn param_env(&self) -> ty::ParamEnv<'tcx> {
646 fn create_next_universe(&mut self) -> ty::UniverseIndex {
647 self.infcx.create_next_universe()
650 fn next_existential_region_var(&mut self, from_forall: bool) -> ty::Region<'tcx> {
651 let origin = NllRegionVariableOrigin::Existential { from_forall };
652 self.infcx.next_nll_region_var(origin)
655 fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> {
656 self.infcx.tcx.mk_region(ty::RePlaceholder(placeholder))
659 fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> {
660 self.infcx.next_nll_region_var_in_universe(
661 NllRegionVariableOrigin::Existential { from_forall: false },
666 fn push_outlives(&mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>) {
667 self.obligations.push(Obligation {
668 cause: self.cause.clone(),
669 param_env: self.param_env,
670 predicate: ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(sup, sub))
671 .to_predicate(self.infcx.tcx),
676 fn const_equate(&mut self, _a: &'tcx Const<'tcx>, _b: &'tcx Const<'tcx>) {
678 self.cause.span(self.infcx.tcx),
679 "lazy_normalization_consts: unreachable `const_equate`"
683 fn normalization() -> NormalizationStrategy {
684 NormalizationStrategy::Eager
687 fn forbid_inference_vars() -> bool {