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