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