src/librustc_infer/infer/canonical/query_response.rs

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