1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! This module contains the code to instantiate a "query result", and
12 //! in particular to extract out the resulting region obligations and
13 //! encode them therein.
15 //! For an overview of what canonicaliation is and how it fits into
16 //! rustc, check out the [chapter in the rustc guide][c].
18 //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
20 use infer::canonical::substitute::substitute_value;
21 use infer::canonical::{
22 Canonical, CanonicalVarKind, CanonicalVarValues, CanonicalizedQueryResult, Certainty,
23 QueryRegionConstraint, QueryResult, SmallCanonicalVarValues,
25 use infer::region_constraints::{Constraint, RegionConstraintData};
26 use infer::InferCtxtBuilder;
27 use infer::{InferCtxt, InferOk, InferResult};
28 use rustc_data_structures::indexed_vec::Idx;
29 use rustc_data_structures::indexed_vec::IndexVec;
30 use rustc_data_structures::sync::Lrc;
32 use syntax_pos::DUMMY_SP;
33 use traits::query::{Fallible, NoSolution};
34 use traits::{FulfillmentContext, TraitEngine};
35 use traits::{Obligation, ObligationCause, PredicateObligation};
36 use ty::fold::TypeFoldable;
37 use ty::subst::{Kind, UnpackedKind};
38 use ty::{self, CanonicalVar, Lift, Ty, TyCtxt};
40 impl<'cx, 'gcx, 'tcx> InferCtxtBuilder<'cx, 'gcx, 'tcx> {
41 /// The "main method" for a canonicalized trait query. Given the
42 /// canonical key `canonical_key`, this method will create a new
43 /// inference context, instantiate the key, and run your operation
44 /// `op`. The operation should yield up a result (of type `R`) as
45 /// well as a set of trait obligations that must be fully
46 /// satisfied. These obligations will be processed and the
47 /// canonical result created.
49 /// Returns `NoSolution` in the event of any error.
51 /// (It might be mildly nicer to implement this on `TyCtxt`, and
52 /// not `InferCtxtBuilder`, but that is a bit tricky right now.
53 /// In part because we would need a `for<'gcx: 'tcx>` sort of
54 /// bound for the closure and in part because it is convenient to
55 /// have `'tcx` be free on this function so that we can talk about
56 /// `K: TypeFoldable<'tcx>`.)
57 pub fn enter_canonical_trait_query<K, R>(
59 canonical_key: &Canonical<'tcx, K>,
60 operation: impl FnOnce(&InferCtxt<'_, 'gcx, 'tcx>, &mut FulfillmentContext<'tcx>, K)
62 ) -> Fallible<CanonicalizedQueryResult<'gcx, R>>
64 K: TypeFoldable<'tcx>,
65 R: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
67 self.enter(|ref infcx| {
68 let (key, canonical_inference_vars) =
69 infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &canonical_key);
70 let fulfill_cx = &mut FulfillmentContext::new();
71 let value = operation(infcx, fulfill_cx, key)?;
72 infcx.make_canonicalized_query_result(canonical_inference_vars, value, fulfill_cx)
77 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
78 /// This method is meant to be invoked as the final step of a canonical query
79 /// implementation. It is given:
81 /// - the instantiated variables `inference_vars` created from the query key
82 /// - the result `answer` of the query
83 /// - a fulfillment context `fulfill_cx` that may contain various obligations which
84 /// have yet to be proven.
86 /// Given this, the function will process the obligations pending
89 /// - If all the obligations can be proven successfully, it will
90 /// package up any resulting region obligations (extracted from
91 /// `infcx`) along with the fully resolved value `answer` into a
92 /// query result (which is then itself canonicalized).
93 /// - If some obligations can be neither proven nor disproven, then
94 /// the same thing happens, but the resulting query is marked as ambiguous.
95 /// - Finally, if any of the obligations result in a hard error,
96 /// then `Err(NoSolution)` is returned.
97 pub fn make_canonicalized_query_result<T>(
99 inference_vars: CanonicalVarValues<'tcx>,
101 fulfill_cx: &mut FulfillmentContext<'tcx>,
102 ) -> Fallible<CanonicalizedQueryResult<'gcx, T>>
104 T: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
106 let query_result = self.make_query_result(inference_vars, answer, fulfill_cx)?;
107 let canonical_result = self.canonicalize_response(&query_result);
110 "make_canonicalized_query_result: canonical_result = {:#?}",
114 Ok(Lrc::new(canonical_result))
117 /// Helper for `make_canonicalized_query_result` that does
118 /// everything up until the final canonicalization.
119 fn make_query_result<T>(
121 inference_vars: CanonicalVarValues<'tcx>,
123 fulfill_cx: &mut FulfillmentContext<'tcx>,
124 ) -> Result<QueryResult<'tcx, T>, NoSolution>
126 T: Debug + TypeFoldable<'tcx> + Lift<'gcx>,
132 inference_vars={:?}, \
134 inference_vars, answer,
137 // Select everything, returning errors.
138 let true_errors = match fulfill_cx.select_where_possible(self) {
140 Err(errors) => errors,
142 debug!("true_errors = {:#?}", true_errors);
144 if !true_errors.is_empty() {
145 // FIXME -- we don't indicate *why* we failed to solve
146 debug!("make_query_result: true_errors={:#?}", true_errors);
147 return Err(NoSolution);
150 // Anything left unselected *now* must be an ambiguity.
151 let ambig_errors = match fulfill_cx.select_all_or_error(self) {
153 Err(errors) => errors,
155 debug!("ambig_errors = {:#?}", ambig_errors);
157 let region_obligations = self.take_registered_region_obligations();
158 let region_constraints = self.with_region_constraints(|region_constraints| {
163 .map(|(_, r_o)| (r_o.sup_type, r_o.sub_region)),
167 let certainty = if ambig_errors.is_empty() {
174 var_values: inference_vars,
181 /// Given the (canonicalized) result to a canonical query,
182 /// instantiates the result so it can be used, plugging in the
183 /// values from the canonical query. (Note that the result may
184 /// have been ambiguous; you should check the certainty level of
185 /// the query before applying this function.)
187 /// To get a good understanding of what is happening here, check
188 /// out the [chapter in the rustc guide][c].
190 /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#processing-the-canonicalized-query-result
191 pub fn instantiate_query_result_and_region_obligations<R>(
193 cause: &ObligationCause<'tcx>,
194 param_env: ty::ParamEnv<'tcx>,
195 original_values: &SmallCanonicalVarValues<'tcx>,
196 query_result: &Canonical<'tcx, QueryResult<'tcx, R>>,
197 ) -> InferResult<'tcx, R>
199 R: Debug + TypeFoldable<'tcx>,
204 } = self.query_result_substitution(cause, param_env, original_values, query_result)?;
206 obligations.extend(self.query_region_constraints_into_obligations(
209 &query_result.value.region_constraints,
214 query_result.substitute_projected(self.tcx, &result_subst, |q_r| &q_r.value);
222 /// An alternative to
223 /// `instantiate_query_result_and_region_obligations` that is more
224 /// efficient for NLL. NLL is a bit more advanced in the
225 /// "transition to chalk" than the rest of the compiler. During
226 /// the NLL type check, all of the "processing" of types and
227 /// things happens in queries -- the NLL checker itself is only
228 /// interested in the region obligations (`'a: 'b` or `T: 'b`)
229 /// that come out of these queries, which it wants to convert into
230 /// MIR-based constraints and solve. Therefore, it is most
231 /// convenient for the NLL Type Checker to **directly consume**
232 /// the `QueryRegionConstraint` values that arise from doing a
233 /// query. This is contrast to other parts of the compiler, which
234 /// would prefer for those `QueryRegionConstraint` to be converted
235 /// into the older infcx-style constraints (e.g., calls to
236 /// `sub_regions` or `register_region_obligation`).
238 /// Therefore, `instantiate_nll_query_result_and_region_obligations` performs the same
239 /// basic operations as `instantiate_query_result_and_region_obligations` but
240 /// it returns its result differently:
242 /// - It creates a substitution `S` that maps from the original
243 /// query variables to the values computed in the query
244 /// result. If any errors arise, they are propagated back as an
246 /// - In the case of a successful substitution, we will append
247 /// `QueryRegionConstraint` values onto the
248 /// `output_query_region_constraints` vector for the solver to
249 /// use (if an error arises, some values may also be pushed, but
250 /// they should be ignored).
251 /// - It **can happen** (though it rarely does currently) that
252 /// equating types and things will give rise to subobligations
253 /// that must be processed. In this case, those subobligations
254 /// are propagated back in the return value.
255 /// - Finally, the query result (of type `R`) is propagated back,
256 /// after applying the substitution `S`.
257 pub fn instantiate_nll_query_result_and_region_obligations<R>(
259 cause: &ObligationCause<'tcx>,
260 param_env: ty::ParamEnv<'tcx>,
261 original_values: &SmallCanonicalVarValues<'tcx>,
262 query_result: &Canonical<'tcx, QueryResult<'tcx, R>>,
263 output_query_region_constraints: &mut Vec<QueryRegionConstraint<'tcx>>,
264 ) -> InferResult<'tcx, R>
266 R: Debug + TypeFoldable<'tcx>,
268 // In an NLL query, there should be no type variables in the
269 // query, only region variables.
270 debug_assert!(query_result.variables.iter().all(|v| match v.kind {
271 CanonicalVarKind::Ty(_) => false,
272 CanonicalVarKind::Region => true,
276 self.query_result_substitution_guess(cause, original_values, query_result);
278 // Compute `QueryRegionConstraint` values that unify each of
279 // the original values `v_o` that was canonicalized into a
281 let mut obligations = vec![];
283 for (index, original_value) in original_values.iter().enumerate() {
284 // ...with the value `v_r` of that variable from the query.
285 let result_value = query_result.substitute_projected(self.tcx, &result_subst, |v| {
286 &v.var_values[CanonicalVar::new(index)]
288 match (original_value.unpack(), result_value.unpack()) {
289 (UnpackedKind::Lifetime(ty::ReErased), UnpackedKind::Lifetime(ty::ReErased)) => {
293 (UnpackedKind::Lifetime(v_o), UnpackedKind::Lifetime(v_r)) => {
294 // To make `v_o = v_r`, we emit `v_o: v_r` and `v_r: v_o`.
296 output_query_region_constraints
297 .push(ty::Binder::dummy(ty::OutlivesPredicate(v_o.into(), v_r)));
298 output_query_region_constraints
299 .push(ty::Binder::dummy(ty::OutlivesPredicate(v_r.into(), v_o)));
303 (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => {
304 let ok = self.at(cause, param_env).eq(v1, v2)?;
305 obligations.extend(ok.into_obligations());
310 "kind mismatch, cannot unify {:?} and {:?}",
318 // ...also include the other query region constraints from the query.
319 output_query_region_constraints.reserve(query_result.value.region_constraints.len());
320 for r_c in query_result.value.region_constraints.iter() {
321 let &ty::OutlivesPredicate(k1, r2) = r_c.skip_binder(); // reconstructed below
322 let k1 = substitute_value(self.tcx, &result_subst, &k1);
323 let r2 = substitute_value(self.tcx, &result_subst, &r2);
325 output_query_region_constraints
326 .push(ty::Binder::bind(ty::OutlivesPredicate(k1, r2)));
331 query_result.substitute_projected(self.tcx, &result_subst, |q_r| &q_r.value);
339 /// Given the original values and the (canonicalized) result from
340 /// computing a query, returns a substitution that can be applied
341 /// to the query result to convert the result back into the
342 /// original namespace.
344 /// The substitution also comes accompanied with subobligations
345 /// that arose from unification; these might occur if (for
346 /// example) we are doing lazy normalization and the value
347 /// assigned to a type variable is unified with an unnormalized
349 fn query_result_substitution<R>(
351 cause: &ObligationCause<'tcx>,
352 param_env: ty::ParamEnv<'tcx>,
353 original_values: &SmallCanonicalVarValues<'tcx>,
354 query_result: &Canonical<'tcx, QueryResult<'tcx, R>>,
355 ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
357 R: Debug + TypeFoldable<'tcx>,
360 "query_result_substitution(original_values={:#?}, query_result={:#?})",
361 original_values, query_result,
365 self.query_result_substitution_guess(cause, original_values, query_result);
367 let obligations = self.unify_query_result_substitution_guess(
382 /// Given the original values and the (canonicalized) result from
383 /// computing a query, returns a **guess** at a substitution that
384 /// can be applied to the query result to convert the result back
385 /// into the original namespace. This is called a **guess**
386 /// because it uses a quick heuristic to find the values for each
387 /// canonical variable; if that quick heuristic fails, then we
388 /// will instantiate fresh inference variables for each canonical
389 /// variable instead. Therefore, the result of this method must be
391 fn query_result_substitution_guess<R>(
393 cause: &ObligationCause<'tcx>,
394 original_values: &SmallCanonicalVarValues<'tcx>,
395 query_result: &Canonical<'tcx, QueryResult<'tcx, R>>,
396 ) -> CanonicalVarValues<'tcx>
398 R: Debug + TypeFoldable<'tcx>,
401 "query_result_substitution_guess(original_values={:#?}, query_result={:#?})",
402 original_values, query_result,
405 // Every canonical query result includes values for each of
406 // the inputs to the query. Therefore, we begin by unifying
407 // these values with the original inputs that were
409 let result_values = &query_result.value.var_values;
410 assert_eq!(original_values.len(), result_values.len());
412 // Quickly try to find initial values for the canonical
413 // variables in the result in terms of the query. We do this
414 // by iterating down the values that the query gave to each of
415 // the canonical inputs. If we find that one of those values
416 // is directly equal to one of the canonical variables in the
417 // result, then we can type the corresponding value from the
418 // input. See the example above.
419 let mut opt_values: IndexVec<CanonicalVar, Option<Kind<'tcx>>> =
420 IndexVec::from_elem_n(None, query_result.variables.len());
422 // In terms of our example above, we are iterating over pairs like:
423 // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)]
424 for (original_value, result_value) in original_values.iter().zip(result_values) {
425 match result_value.unpack() {
426 UnpackedKind::Type(result_value) => {
427 // e.g., here `result_value` might be `?0` in the example above...
428 if let ty::Infer(ty::InferTy::CanonicalTy(index)) = result_value.sty {
429 // in which case we would set `canonical_vars[0]` to `Some(?U)`.
430 opt_values[index] = Some(*original_value);
433 UnpackedKind::Lifetime(result_value) => {
434 // e.g., here `result_value` might be `'?1` in the example above...
435 if let &ty::RegionKind::ReCanonical(index) = result_value {
436 // in which case we would set `canonical_vars[0]` to `Some('static)`.
437 opt_values[index] = Some(*original_value);
443 // Create a result substitution: if we found a value for a
444 // given variable in the loop above, use that. Otherwise, use
445 // a fresh inference variable.
446 let result_subst = CanonicalVarValues {
447 var_values: query_result
451 .map(|(index, info)| match opt_values[CanonicalVar::new(index)] {
453 None => self.fresh_inference_var_for_canonical_var(cause.span, *info),
461 /// Given a "guess" at the values for the canonical variables in
462 /// the input, try to unify with the *actual* values found in the
463 /// query result. Often, but not always, this is a no-op, because
464 /// we already found the mapping in the "guessing" step.
466 /// See also: `query_result_substitution_guess`
467 fn unify_query_result_substitution_guess<R>(
469 cause: &ObligationCause<'tcx>,
470 param_env: ty::ParamEnv<'tcx>,
471 original_values: &SmallCanonicalVarValues<'tcx>,
472 result_subst: &CanonicalVarValues<'tcx>,
473 query_result: &Canonical<'tcx, QueryResult<'tcx, R>>,
474 ) -> InferResult<'tcx, ()>
476 R: Debug + TypeFoldable<'tcx>,
478 // A closure that yields the result value for the given
479 // canonical variable; this is taken from
480 // `query_result.var_values` after applying the substitution
482 let substituted_query_result = |index: CanonicalVar| -> Kind<'tcx> {
483 query_result.substitute_projected(self.tcx, &result_subst, |v| &v.var_values[index])
486 // Unify the original value for each variable with the value
487 // taken from `query_result` (after applying `result_subst`).
488 Ok(self.unify_canonical_vars(cause, param_env, original_values, substituted_query_result)?)
491 /// Converts the region constraints resulting from a query into an
492 /// iterator of obligations.
493 fn query_region_constraints_into_obligations<'a>(
495 cause: &'a ObligationCause<'tcx>,
496 param_env: ty::ParamEnv<'tcx>,
497 unsubstituted_region_constraints: &'a [QueryRegionConstraint<'tcx>],
498 result_subst: &'a CanonicalVarValues<'tcx>,
499 ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a {
501 unsubstituted_region_constraints
503 .map(move |constraint| {
504 let ty::OutlivesPredicate(k1, r2) = constraint.skip_binder(); // restored below
505 let k1 = substitute_value(self.tcx, result_subst, k1);
506 let r2 = substitute_value(self.tcx, result_subst, r2);
508 UnpackedKind::Lifetime(r1) => Obligation::new(
511 ty::Predicate::RegionOutlives(ty::Binder::dummy(
512 ty::OutlivesPredicate(r1, r2),
516 UnpackedKind::Type(t1) => Obligation::new(
519 ty::Predicate::TypeOutlives(ty::Binder::dummy(ty::OutlivesPredicate(
525 ) as Box<dyn Iterator<Item = _>>
528 /// Given two sets of values for the same set of canonical variables, unify them.
529 /// The second set is produced lazilly by supplying indices from the first set.
530 fn unify_canonical_vars(
532 cause: &ObligationCause<'tcx>,
533 param_env: ty::ParamEnv<'tcx>,
534 variables1: &SmallCanonicalVarValues<'tcx>,
535 variables2: impl Fn(CanonicalVar) -> Kind<'tcx>,
536 ) -> InferResult<'tcx, ()> {
537 self.commit_if_ok(|_| {
538 let mut obligations = vec![];
539 for (index, value1) in variables1.iter().enumerate() {
540 let value2 = variables2(CanonicalVar::new(index));
542 match (value1.unpack(), value2.unpack()) {
543 (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => {
545 .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
548 UnpackedKind::Lifetime(ty::ReErased),
549 UnpackedKind::Lifetime(ty::ReErased),
553 (UnpackedKind::Lifetime(v1), UnpackedKind::Lifetime(v2)) => {
555 .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
558 bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
570 /// Given the region obligations and constraints scraped from the infcx,
571 /// creates query region constraints.
572 pub fn make_query_outlives<'tcx>(
573 tcx: TyCtxt<'_, '_, 'tcx>,
574 outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>)>,
575 region_constraints: &RegionConstraintData<'tcx>,
576 ) -> Vec<QueryRegionConstraint<'tcx>> {
577 let RegionConstraintData {
581 } = region_constraints;
583 assert!(verifys.is_empty());
584 assert!(givens.is_empty());
586 let mut outlives: Vec<_> = constraints
588 .map(|(k, _)| match *k {
589 // Swap regions because we are going from sub (<=) to outlives
591 Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate(
592 tcx.mk_region(ty::ReVar(v2)).into(),
593 tcx.mk_region(ty::ReVar(v1)),
595 Constraint::VarSubReg(v1, r2) => {
596 ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1)))
598 Constraint::RegSubVar(r1, v2) => {
599 ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1)
601 Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1),
603 .map(ty::Binder::dummy) // no bound regions in the code above
608 .map(|(ty, r)| ty::OutlivesPredicate(ty.into(), r))
609 .map(ty::Binder::dummy), // no bound regions in the code above