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