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