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 guide][c].
8 //! [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html
10 use crate::arena::ArenaAllocatable;
11 use crate::infer::canonical::substitute::substitute_value;
12 use crate::infer::canonical::{
13 Canonical, CanonicalVarValues, CanonicalizedQueryResponse, Certainty,
14 OriginalQueryValues, QueryRegionConstraint, QueryResponse,
16 use crate::infer::region_constraints::{Constraint, RegionConstraintData};
17 use crate::infer::InferCtxtBuilder;
18 use crate::infer::{InferCtxt, InferOk, InferResult};
19 use rustc_data_structures::indexed_vec::Idx;
20 use rustc_data_structures::indexed_vec::IndexVec;
22 use syntax_pos::DUMMY_SP;
23 use crate::traits::query::{Fallible, NoSolution};
24 use crate::traits::TraitEngine;
25 use crate::traits::{Obligation, ObligationCause, PredicateObligation};
26 use crate::ty::fold::TypeFoldable;
27 use crate::ty::subst::{Kind, UnpackedKind};
28 use crate::ty::{self, BoundVar, Lift, Ty, TyCtxt};
29 use crate::util::captures::Captures;
31 impl<'cx, 'gcx, 'tcx> InferCtxtBuilder<'cx, 'gcx, 'tcx> {
32 /// The "main method" for a canonicalized trait query. Given the
33 /// canonical key `canonical_key`, this method will create a new
34 /// inference context, instantiate the key, and run your operation
35 /// `op`. The operation should yield up a result (of type `R`) as
36 /// well as a set of trait obligations that must be fully
37 /// satisfied. These obligations will be processed and the
38 /// canonical result created.
40 /// Returns `NoSolution` in the event of any error.
42 /// (It might be mildly nicer to implement this on `TyCtxt`, and
43 /// not `InferCtxtBuilder`, but that is a bit tricky right now.
44 /// In part because we would need a `for<'gcx: 'tcx>` sort of
45 /// bound for the closure and in part because it is convenient to
46 /// have `'tcx` be free on this function so that we can talk about
47 /// `K: TypeFoldable<'tcx>`.)
48 pub fn enter_canonical_trait_query<K, R>(
50 canonical_key: &Canonical<'tcx, K>,
51 operation: impl FnOnce(&InferCtxt<'_, 'gcx, 'tcx>, &mut dyn TraitEngine<'tcx>, K)
53 ) -> Fallible<CanonicalizedQueryResponse<'gcx, R>>
55 K: TypeFoldable<'tcx>,
56 R: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
57 Canonical<'gcx, <QueryResponse<'gcx, R> as Lift<'gcx>>::Lifted>: ArenaAllocatable,
59 self.enter_with_canonical(
62 |ref infcx, key, canonical_inference_vars| {
63 let mut fulfill_cx = TraitEngine::new(infcx.tcx);
64 let value = operation(infcx, &mut *fulfill_cx, key)?;
65 infcx.make_canonicalized_query_response(
66 canonical_inference_vars,
75 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
76 /// This method is meant to be invoked as the final step of a canonical query
77 /// implementation. It is given:
79 /// - the instantiated variables `inference_vars` created from the query key
80 /// - the result `answer` of the query
81 /// - a fulfillment context `fulfill_cx` that may contain various obligations which
82 /// have yet to be proven.
84 /// Given this, the function will process the obligations pending
87 /// - If all the obligations can be proven successfully, it will
88 /// package up any resulting region obligations (extracted from
89 /// `infcx`) along with the fully resolved value `answer` into a
90 /// query result (which is then itself canonicalized).
91 /// - If some obligations can be neither proven nor disproven, then
92 /// the same thing happens, but the resulting query is marked as ambiguous.
93 /// - Finally, if any of the obligations result in a hard error,
94 /// then `Err(NoSolution)` is returned.
95 pub fn make_canonicalized_query_response<T>(
97 inference_vars: CanonicalVarValues<'tcx>,
99 fulfill_cx: &mut dyn TraitEngine<'tcx>,
100 ) -> Fallible<CanonicalizedQueryResponse<'gcx, T>>
102 T: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
103 Canonical<'gcx, <QueryResponse<'gcx, T> as Lift<'gcx>>::Lifted>: ArenaAllocatable,
105 let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?;
106 let canonical_result = self.canonicalize_response(&query_response);
109 "make_canonicalized_query_response: canonical_result = {:#?}",
113 Ok(self.tcx.arena.alloc(canonical_result))
116 /// A version of `make_canonicalized_query_response` that does
117 /// not pack in obligations, for contexts that want to drop
118 /// pending obligations instead of treating them as an ambiguity (e.g.
119 /// typeck "probing" contexts).
121 /// If you DO want to keep track of pending obligations (which
122 /// include all region obligations, so this includes all cases
123 /// that care about regions) with this function, you have to
124 /// do it yourself, by e.g., having them be a part of the answer.
125 pub fn make_query_response_ignoring_pending_obligations<T>(
127 inference_vars: CanonicalVarValues<'tcx>,
129 ) -> Canonical<'gcx, QueryResponse<'gcx, <T as Lift<'gcx>>::Lifted>>
131 T: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
133 self.canonicalize_response(&QueryResponse {
134 var_values: inference_vars,
135 region_constraints: vec![],
136 certainty: Certainty::Proven, // Ambiguities are OK!
141 /// Helper for `make_canonicalized_query_response` that does
142 /// everything up until the final canonicalization.
143 fn make_query_response<T>(
145 inference_vars: CanonicalVarValues<'tcx>,
147 fulfill_cx: &mut dyn TraitEngine<'tcx>,
148 ) -> Result<QueryResponse<'tcx, T>, NoSolution>
150 T: Debug + TypeFoldable<'tcx> + Lift<'gcx>,
155 "make_query_response(\
156 inference_vars={:?}, \
158 inference_vars, answer,
161 // Select everything, returning errors.
162 let true_errors = fulfill_cx.select_where_possible(self).err().unwrap_or_else(Vec::new);
163 debug!("true_errors = {:#?}", true_errors);
165 if !true_errors.is_empty() {
166 // FIXME -- we don't indicate *why* we failed to solve
167 debug!("make_query_response: true_errors={:#?}", true_errors);
168 return Err(NoSolution);
171 // Anything left unselected *now* must be an ambiguity.
172 let ambig_errors = fulfill_cx.select_all_or_error(self).err().unwrap_or_else(Vec::new);
173 debug!("ambig_errors = {:#?}", ambig_errors);
175 let region_obligations = self.take_registered_region_obligations();
176 let region_constraints = self.with_region_constraints(|region_constraints| {
181 .map(|(_, r_o)| (r_o.sup_type, r_o.sub_region)),
186 let certainty = if ambig_errors.is_empty() {
193 var_values: inference_vars,
200 /// Given the (canonicalized) result to a canonical query,
201 /// instantiates the result so it can be used, plugging in the
202 /// values from the canonical query. (Note that the result may
203 /// have been ambiguous; you should check the certainty level of
204 /// the query before applying this function.)
206 /// To get a good understanding of what is happening here, check
207 /// out the [chapter in the rustc guide][c].
209 /// [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html#processing-the-canonicalized-query-result
210 pub fn instantiate_query_response_and_region_obligations<R>(
212 cause: &ObligationCause<'tcx>,
213 param_env: ty::ParamEnv<'tcx>,
214 original_values: &OriginalQueryValues<'tcx>,
215 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
216 ) -> InferResult<'tcx, R>
218 R: Debug + TypeFoldable<'tcx>,
223 } = self.query_response_substitution(cause, param_env, original_values, query_response)?;
225 obligations.extend(self.query_region_constraints_into_obligations(
228 &query_response.value.region_constraints,
233 query_response.substitute_projected(self.tcx, &result_subst, |q_r| &q_r.value);
241 /// An alternative to
242 /// `instantiate_query_response_and_region_obligations` that is more
243 /// efficient for NLL. NLL is a bit more advanced in the
244 /// "transition to chalk" than the rest of the compiler. During
245 /// the NLL type check, all of the "processing" of types and
246 /// things happens in queries -- the NLL checker itself is only
247 /// interested in the region obligations (`'a: 'b` or `T: 'b`)
248 /// that come out of these queries, which it wants to convert into
249 /// MIR-based constraints and solve. Therefore, it is most
250 /// convenient for the NLL Type Checker to **directly consume**
251 /// the `QueryRegionConstraint` values that arise from doing a
252 /// query. This is contrast to other parts of the compiler, which
253 /// would prefer for those `QueryRegionConstraint` to be converted
254 /// into the older infcx-style constraints (e.g., calls to
255 /// `sub_regions` or `register_region_obligation`).
257 /// Therefore, `instantiate_nll_query_response_and_region_obligations` performs the same
258 /// basic operations as `instantiate_query_response_and_region_obligations` but
259 /// it returns its result differently:
261 /// - It creates a substitution `S` that maps from the original
262 /// query variables to the values computed in the query
263 /// result. If any errors arise, they are propagated back as an
265 /// - In the case of a successful substitution, we will append
266 /// `QueryRegionConstraint` values onto the
267 /// `output_query_region_constraints` vector for the solver to
268 /// use (if an error arises, some values may also be pushed, but
269 /// they should be ignored).
270 /// - It **can happen** (though it rarely does currently) that
271 /// equating types and things will give rise to subobligations
272 /// that must be processed. In this case, those subobligations
273 /// are propagated back in the return value.
274 /// - Finally, the query result (of type `R`) is propagated back,
275 /// after applying the substitution `S`.
276 pub fn instantiate_nll_query_response_and_region_obligations<R>(
278 cause: &ObligationCause<'tcx>,
279 param_env: ty::ParamEnv<'tcx>,
280 original_values: &OriginalQueryValues<'tcx>,
281 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
282 output_query_region_constraints: &mut Vec<QueryRegionConstraint<'tcx>>,
283 ) -> InferResult<'tcx, R>
285 R: Debug + TypeFoldable<'tcx>,
288 self.query_response_substitution_guess(cause, original_values, query_response);
290 // Compute `QueryRegionConstraint` values that unify each of
291 // the original values `v_o` that was canonicalized into a
293 let mut obligations = vec![];
295 for (index, original_value) in original_values.var_values.iter().enumerate() {
296 // ...with the value `v_r` of that variable from the query.
297 let result_value = query_response.substitute_projected(self.tcx, &result_subst, |v| {
298 &v.var_values[BoundVar::new(index)]
300 match (original_value.unpack(), result_value.unpack()) {
301 (UnpackedKind::Lifetime(ty::ReErased), UnpackedKind::Lifetime(ty::ReErased)) => {
305 (UnpackedKind::Lifetime(v_o), UnpackedKind::Lifetime(v_r)) => {
306 // To make `v_o = v_r`, we emit `v_o: v_r` and `v_r: v_o`.
308 output_query_region_constraints
309 .push(ty::Binder::dummy(ty::OutlivesPredicate(v_o.into(), v_r)));
310 output_query_region_constraints
311 .push(ty::Binder::dummy(ty::OutlivesPredicate(v_r.into(), v_o)));
315 (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => {
316 let ok = self.at(cause, param_env).eq(v1, v2)?;
317 obligations.extend(ok.into_obligations());
320 (UnpackedKind::Const(..), UnpackedKind::Const(..)) => {
321 unimplemented!() // FIXME(const_generics)
326 "kind mismatch, cannot unify {:?} and {:?}",
334 // ...also include the other query region constraints from the query.
335 output_query_region_constraints.extend(
336 query_response.value.region_constraints.iter().filter_map(|r_c| {
337 let r_c = substitute_value(self.tcx, &result_subst, r_c);
339 // Screen out `'a: 'a` cases -- we skip the binder here but
340 // only care the inner values to one another, so they are still at
341 // consistent binding levels.
342 let &ty::OutlivesPredicate(k1, r2) = r_c.skip_binder();
352 query_response.substitute_projected(self.tcx, &result_subst, |q_r| &q_r.value);
360 /// Given the original values and the (canonicalized) result from
361 /// computing a query, returns a substitution that can be applied
362 /// to the query result to convert the result back into the
363 /// original namespace.
365 /// The substitution also comes accompanied with subobligations
366 /// that arose from unification; these might occur if (for
367 /// example) we are doing lazy normalization and the value
368 /// assigned to a type variable is unified with an unnormalized
370 fn query_response_substitution<R>(
372 cause: &ObligationCause<'tcx>,
373 param_env: ty::ParamEnv<'tcx>,
374 original_values: &OriginalQueryValues<'tcx>,
375 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
376 ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
378 R: Debug + TypeFoldable<'tcx>,
381 "query_response_substitution(original_values={:#?}, query_response={:#?})",
382 original_values, query_response,
386 self.query_response_substitution_guess(cause, original_values, query_response);
388 let obligations = self.unify_query_response_substitution_guess(
403 /// Given the original values and the (canonicalized) result from
404 /// computing a query, returns a **guess** at a substitution that
405 /// can be applied to the query result to convert the result back
406 /// into the original namespace. This is called a **guess**
407 /// because it uses a quick heuristic to find the values for each
408 /// canonical variable; if that quick heuristic fails, then we
409 /// will instantiate fresh inference variables for each canonical
410 /// variable instead. Therefore, the result of this method must be
412 fn query_response_substitution_guess<R>(
414 cause: &ObligationCause<'tcx>,
415 original_values: &OriginalQueryValues<'tcx>,
416 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
417 ) -> CanonicalVarValues<'tcx>
419 R: Debug + TypeFoldable<'tcx>,
422 "query_response_substitution_guess(original_values={:#?}, query_response={:#?})",
423 original_values, query_response,
426 // For each new universe created in the query result that did
427 // not appear in the original query, create a local
429 let mut universe_map = original_values.universe_map.clone();
430 let num_universes_in_query = original_values.universe_map.len();
431 let num_universes_in_response = query_response.max_universe.as_usize() + 1;
432 for _ in num_universes_in_query..num_universes_in_response {
433 universe_map.push(self.create_next_universe());
435 assert!(universe_map.len() >= 1); // always have the root universe
437 universe_map[ty::UniverseIndex::ROOT.as_usize()],
438 ty::UniverseIndex::ROOT
441 // Every canonical query result includes values for each of
442 // the inputs to the query. Therefore, we begin by unifying
443 // these values with the original inputs that were
445 let result_values = &query_response.value.var_values;
446 assert_eq!(original_values.var_values.len(), result_values.len());
448 // Quickly try to find initial values for the canonical
449 // variables in the result in terms of the query. We do this
450 // by iterating down the values that the query gave to each of
451 // the canonical inputs. If we find that one of those values
452 // is directly equal to one of the canonical variables in the
453 // result, then we can type the corresponding value from the
454 // input. See the example above.
455 let mut opt_values: IndexVec<BoundVar, Option<Kind<'tcx>>> =
456 IndexVec::from_elem_n(None, query_response.variables.len());
458 // In terms of our example above, we are iterating over pairs like:
459 // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)]
460 for (original_value, result_value) in original_values.var_values.iter().zip(result_values) {
461 match result_value.unpack() {
462 UnpackedKind::Type(result_value) => {
463 // e.g., here `result_value` might be `?0` in the example above...
464 if let ty::Bound(debruijn, b) = result_value.sty {
465 // ...in which case we would set `canonical_vars[0]` to `Some(?U)`.
467 // We only allow a `ty::INNERMOST` index in substitutions.
468 assert_eq!(debruijn, ty::INNERMOST);
469 opt_values[b.var] = Some(*original_value);
472 UnpackedKind::Lifetime(result_value) => {
473 // e.g., here `result_value` might be `'?1` in the example above...
474 if let &ty::RegionKind::ReLateBound(debruijn, br) = result_value {
475 // ... in which case we would set `canonical_vars[0]` to `Some('static)`.
477 // We only allow a `ty::INNERMOST` index in substitutions.
478 assert_eq!(debruijn, ty::INNERMOST);
479 opt_values[br.assert_bound_var()] = Some(*original_value);
482 UnpackedKind::Const(..) => {
483 unimplemented!() // FIXME(const_generics)
488 // Create a result substitution: if we found a value for a
489 // given variable in the loop above, use that. Otherwise, use
490 // a fresh inference variable.
491 let result_subst = CanonicalVarValues {
492 var_values: query_response
496 .map(|(index, info)| {
497 if info.is_existential() {
498 match opt_values[BoundVar::new(index)] {
500 None => self.instantiate_canonical_var(cause.span, *info, |u| {
501 universe_map[u.as_usize()]
505 self.instantiate_canonical_var(cause.span, *info, |u| {
506 universe_map[u.as_usize()]
516 /// Given a "guess" at the values for the canonical variables in
517 /// the input, try to unify with the *actual* values found in the
518 /// query result. Often, but not always, this is a no-op, because
519 /// we already found the mapping in the "guessing" step.
521 /// See also: `query_response_substitution_guess`
522 fn unify_query_response_substitution_guess<R>(
524 cause: &ObligationCause<'tcx>,
525 param_env: ty::ParamEnv<'tcx>,
526 original_values: &OriginalQueryValues<'tcx>,
527 result_subst: &CanonicalVarValues<'tcx>,
528 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
529 ) -> InferResult<'tcx, ()>
531 R: Debug + TypeFoldable<'tcx>,
533 // A closure that yields the result value for the given
534 // canonical variable; this is taken from
535 // `query_response.var_values` after applying the substitution
537 let substituted_query_response = |index: BoundVar| -> Kind<'tcx> {
538 query_response.substitute_projected(self.tcx, &result_subst, |v| &v.var_values[index])
541 // Unify the original value for each variable with the value
542 // taken from `query_response` (after applying `result_subst`).
543 Ok(self.unify_canonical_vars(
547 substituted_query_response,
551 /// Converts the region constraints resulting from a query into an
552 /// iterator of obligations.
553 fn query_region_constraints_into_obligations<'a>(
555 cause: &'a ObligationCause<'tcx>,
556 param_env: ty::ParamEnv<'tcx>,
557 unsubstituted_region_constraints: &'a [QueryRegionConstraint<'tcx>],
558 result_subst: &'a CanonicalVarValues<'tcx>,
559 ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a + Captures<'gcx> {
560 unsubstituted_region_constraints
562 .map(move |constraint| {
563 let constraint = substitute_value(self.tcx, result_subst, constraint);
564 let &ty::OutlivesPredicate(k1, r2) = constraint.skip_binder(); // restored below
570 UnpackedKind::Lifetime(r1) => ty::Predicate::RegionOutlives(
572 ty::OutlivesPredicate(r1, r2)
575 UnpackedKind::Type(t1) => ty::Predicate::TypeOutlives(
577 ty::OutlivesPredicate(t1, r2)
580 UnpackedKind::Const(..) => {
581 // Consts cannot outlive one another, so we don't expect to
582 // ecounter this branch.
583 span_bug!(cause.span, "unexpected const outlives {:?}", constraint);
590 /// Given two sets of values for the same set of canonical variables, unify them.
591 /// The second set is produced lazily by supplying indices from the first set.
592 fn unify_canonical_vars(
594 cause: &ObligationCause<'tcx>,
595 param_env: ty::ParamEnv<'tcx>,
596 variables1: &OriginalQueryValues<'tcx>,
597 variables2: impl Fn(BoundVar) -> Kind<'tcx>,
598 ) -> InferResult<'tcx, ()> {
599 self.commit_if_ok(|_| {
600 let mut obligations = vec![];
601 for (index, value1) in variables1.var_values.iter().enumerate() {
602 let value2 = variables2(BoundVar::new(index));
604 match (value1.unpack(), value2.unpack()) {
605 (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => {
607 .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
610 UnpackedKind::Lifetime(ty::ReErased),
611 UnpackedKind::Lifetime(ty::ReErased),
615 (UnpackedKind::Lifetime(v1), UnpackedKind::Lifetime(v2)) => {
617 .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
619 (UnpackedKind::Const(..), UnpackedKind::Const(..)) => {
620 unimplemented!() // FIXME(const_generics)
623 bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
635 /// Given the region obligations and constraints scraped from the infcx,
636 /// creates query region constraints.
637 pub fn make_query_outlives<'tcx>(
638 tcx: TyCtxt<'_, '_, 'tcx>,
639 outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>)>,
640 region_constraints: &RegionConstraintData<'tcx>,
641 ) -> Vec<QueryRegionConstraint<'tcx>> {
642 let RegionConstraintData {
646 } = region_constraints;
648 assert!(verifys.is_empty());
649 assert!(givens.is_empty());
651 let outlives: Vec<_> = constraints
653 .map(|(k, _)| match *k {
654 // Swap regions because we are going from sub (<=) to outlives
656 Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate(
657 tcx.mk_region(ty::ReVar(v2)).into(),
658 tcx.mk_region(ty::ReVar(v1)),
660 Constraint::VarSubReg(v1, r2) => {
661 ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1)))
663 Constraint::RegSubVar(r1, v2) => {
664 ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1)
666 Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1),
668 .map(ty::Binder::dummy) // no bound vars in the code above
671 .map(|(ty, r)| ty::OutlivesPredicate(ty.into(), r))
672 .map(ty::Binder::dummy) // no bound vars in the code above