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