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, CanonicalQueryResponse, CanonicalVarValues, 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::{Obligation, ObligationCause, PredicateObligation};
  20 use crate::traits::{PredicateObligations, TraitEngine, TraitEngineExt};
  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::fold::TypeFoldable;
  27 use rustc_middle::ty::relate::TypeRelation;
  28 use rustc_middle::ty::subst::{GenericArg, GenericArgKind};
  29 use rustc_middle::ty::{self, BoundVar, ToPredicate, Ty, TyCtxt};
  30 use rustc_span::Span;
  31 use std::fmt::Debug;
  32 use std::iter;
  33
  34 impl<'tcx> InferCtxt<'tcx> {
  35     /// This method is meant to be invoked as the final step of a canonical query
  36     /// implementation. It is given:
  37     ///
  38     /// - the instantiated variables `inference_vars` created from the query key
  39     /// - the result `answer` of the query
  40     /// - a fulfillment context `fulfill_cx` that may contain various obligations which
  41     ///   have yet to be proven.
  42     ///
  43     /// Given this, the function will process the obligations pending
  44     /// in `fulfill_cx`:
  45     ///
  46     /// - If all the obligations can be proven successfully, it will
  47     ///   package up any resulting region obligations (extracted from
  48     ///   `infcx`) along with the fully resolved value `answer` into a
  49     ///   query result (which is then itself canonicalized).
  50     /// - If some obligations can be neither proven nor disproven, then
  51     ///   the same thing happens, but the resulting query is marked as ambiguous.
  52     /// - Finally, if any of the obligations result in a hard error,
  53     ///   then `Err(NoSolution)` is returned.
  54     #[instrument(skip(self, inference_vars, answer, fulfill_cx), level = "trace")]
  55     pub fn make_canonicalized_query_response<T>(
  56         &self,
  57         inference_vars: CanonicalVarValues<'tcx>,
  58         answer: T,
  59         fulfill_cx: &mut dyn TraitEngine<'tcx>,
  60     ) -> Fallible<CanonicalQueryResponse<'tcx, T>>
  61     where
  62         T: Debug + TypeFoldable<'tcx>,
  63         Canonical<'tcx, QueryResponse<'tcx, T>>: ArenaAllocatable<'tcx>,
  64     {
  65         let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?;
  66         debug!("query_response = {:#?}", query_response);
  67         let canonical_result = self.canonicalize_response(query_response);
  68         debug!("canonical_result = {:#?}", canonical_result);
  69
  70         Ok(self.tcx.arena.alloc(canonical_result))
  71     }
  72
  73     /// A version of `make_canonicalized_query_response` that does
  74     /// not pack in obligations, for contexts that want to drop
  75     /// pending obligations instead of treating them as an ambiguity (e.g.
  76     /// typeck "probing" contexts).
  77     ///
  78     /// If you DO want to keep track of pending obligations (which
  79     /// include all region obligations, so this includes all cases
  80     /// that care about regions) with this function, you have to
  81     /// do it yourself, by e.g., having them be a part of the answer.
  82     pub fn make_query_response_ignoring_pending_obligations<T>(
  83         &self,
  84         inference_vars: CanonicalVarValues<'tcx>,
  85         answer: T,
  86     ) -> Canonical<'tcx, QueryResponse<'tcx, T>>
  87     where
  88         T: Debug + TypeFoldable<'tcx>,
  89     {
  90         self.canonicalize_response(QueryResponse {
  91             var_values: inference_vars,
  92             region_constraints: QueryRegionConstraints::default(),
  93             certainty: Certainty::Proven, // Ambiguities are OK!
  94             opaque_types: vec![],
  95             value: answer,
  96         })
  97     }
  98
  99     /// Helper for `make_canonicalized_query_response` that does
 100     /// everything up until the final canonicalization.
 101     #[instrument(skip(self, fulfill_cx), level = "debug")]
 102     fn make_query_response<T>(
 103         &self,
 104         inference_vars: CanonicalVarValues<'tcx>,
 105         answer: T,
 106         fulfill_cx: &mut dyn TraitEngine<'tcx>,
 107     ) -> Result<QueryResponse<'tcx, T>, NoSolution>
 108     where
 109         T: Debug + TypeFoldable<'tcx>,
 110     {
 111         let tcx = self.tcx;
 112
 113         // Select everything, returning errors.
 114         let true_errors = fulfill_cx.select_where_possible(self);
 115         debug!("true_errors = {:#?}", true_errors);
 116
 117         if !true_errors.is_empty() {
 118             // FIXME -- we don't indicate *why* we failed to solve
 119             debug!("make_query_response: true_errors={:#?}", true_errors);
 120             return Err(NoSolution);
 121         }
 122
 123         // Anything left unselected *now* must be an ambiguity.
 124         let ambig_errors = fulfill_cx.select_all_or_error(self);
 125         debug!("ambig_errors = {:#?}", ambig_errors);
 126
 127         let region_obligations = self.take_registered_region_obligations();
 128         debug!(?region_obligations);
 129         let region_constraints = self.with_region_constraints(|region_constraints| {
 130             make_query_region_constraints(
 131                 tcx,
 132                 region_obligations
 133                     .iter()
 134                     .map(|r_o| (r_o.sup_type, r_o.sub_region, r_o.origin.to_constraint_category())),
 135                 region_constraints,
 136             )
 137         });
 138         debug!(?region_constraints);
 139
 140         let certainty =
 141             if ambig_errors.is_empty() { Certainty::Proven } else { Certainty::Ambiguous };
 142
 143         let opaque_types = self.take_opaque_types_for_query_response();
 144
 145         Ok(QueryResponse {
 146             var_values: inference_vars,
 147             region_constraints,
 148             certainty,
 149             value: answer,
 150             opaque_types,
 151         })
 152     }
 153
 154     /// FIXME: This method should only be used for canonical queries and therefore be private.
 155     ///
 156     /// As the new solver does canonicalization slightly differently, this is also used there
 157     /// for now. This should hopefully change fairly soon.
 158     pub fn take_opaque_types_for_query_response(&self) -> Vec<(Ty<'tcx>, Ty<'tcx>)> {
 159         std::mem::take(&mut self.inner.borrow_mut().opaque_type_storage.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
 272                             .outlives
 273                             .push((ty::OutlivesPredicate(v_o.into(), v_r), constraint_category));
 274                         output_query_region_constraints
 275                             .outlives
 276                             .push((ty::OutlivesPredicate(v_r.into(), v_o), constraint_category));
 277                     }
 278                 }
 279
 280                 (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
 281                     TypeRelating::new(
 282                         self,
 283                         QueryTypeRelatingDelegate {
 284                             infcx: self,
 285                             param_env,
 286                             cause,
 287                             obligations: &mut obligations,
 288                         },
 289                         ty::Variance::Invariant,
 290                     )
 291                     .relate(v1, v2)?;
 292                 }
 293
 294                 (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
 295                     TypeRelating::new(
 296                         self,
 297                         QueryTypeRelatingDelegate {
 298                             infcx: self,
 299                             param_env,
 300                             cause,
 301                             obligations: &mut obligations,
 302                         },
 303                         ty::Variance::Invariant,
 304                     )
 305                     .relate(v1, v2)?;
 306                 }
 307
 308                 _ => {
 309                     bug!("kind mismatch, cannot unify {:?} and {:?}", original_value, result_value);
 310                 }
 311             }
 312         }
 313
 314         // ...also include the other query region constraints from the query.
 315         output_query_region_constraints.outlives.extend(
 316             query_response.value.region_constraints.outlives.iter().filter_map(|&r_c| {
 317                 let r_c = substitute_value(self.tcx, &result_subst, r_c);
 318
 319                 // Screen out `'a: 'a` cases.
 320                 let ty::OutlivesPredicate(k1, r2) = r_c.0;
 321                 if k1 != r2.into() { Some(r_c) } else { None }
 322             }),
 323         );
 324
 325         // ...also include the query member constraints.
 326         output_query_region_constraints.member_constraints.extend(
 327             query_response
 328                 .value
 329                 .region_constraints
 330                 .member_constraints
 331                 .iter()
 332                 .map(|p_c| substitute_value(self.tcx, &result_subst, p_c.clone())),
 333         );
 334
 335         let user_result: R =
 336             query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone());
 337
 338         Ok(InferOk { value: user_result, obligations })
 339     }
 340
 341     /// Given the original values and the (canonicalized) result from
 342     /// computing a query, returns a substitution that can be applied
 343     /// to the query result to convert the result back into the
 344     /// original namespace.
 345     ///
 346     /// The substitution also comes accompanied with subobligations
 347     /// that arose from unification; these might occur if (for
 348     /// example) we are doing lazy normalization and the value
 349     /// assigned to a type variable is unified with an unnormalized
 350     /// projection.
 351     fn query_response_substitution<R>(
 352         &self,
 353         cause: &ObligationCause<'tcx>,
 354         param_env: ty::ParamEnv<'tcx>,
 355         original_values: &OriginalQueryValues<'tcx>,
 356         query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
 357     ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
 358     where
 359         R: Debug + TypeFoldable<'tcx>,
 360     {
 361         debug!(
 362             "query_response_substitution(original_values={:#?}, query_response={:#?})",
 363             original_values, query_response,
 364         );
 365
 366         let mut value = self.query_response_substitution_guess(
 367             cause,
 368             param_env,
 369             original_values,
 370             query_response,
 371         )?;
 372
 373         value.obligations.extend(
 374             self.unify_query_response_substitution_guess(
 375                 cause,
 376                 param_env,
 377                 original_values,
 378                 &value.value,
 379                 query_response,
 380             )?
 381             .into_obligations(),
 382         );
 383
 384         Ok(value)
 385     }
 386
 387     /// Given the original values and the (canonicalized) result from
 388     /// computing a query, returns a **guess** at a substitution that
 389     /// can be applied to the query result to convert the result back
 390     /// into the original namespace. This is called a **guess**
 391     /// because it uses a quick heuristic to find the values for each
 392     /// canonical variable; if that quick heuristic fails, then we
 393     /// will instantiate fresh inference variables for each canonical
 394     /// variable instead. Therefore, the result of this method must be
 395     /// properly unified
 396     fn query_response_substitution_guess<R>(
 397         &self,
 398         cause: &ObligationCause<'tcx>,
 399         param_env: ty::ParamEnv<'tcx>,
 400         original_values: &OriginalQueryValues<'tcx>,
 401         query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
 402     ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
 403     where
 404         R: Debug + TypeFoldable<'tcx>,
 405     {
 406         debug!(
 407             "query_response_substitution_guess(original_values={:#?}, query_response={:#?})",
 408             original_values, query_response,
 409         );
 410
 411         // For each new universe created in the query result that did
 412         // not appear in the original query, create a local
 413         // superuniverse.
 414         let mut universe_map = original_values.universe_map.clone();
 415         let num_universes_in_query = original_values.universe_map.len();
 416         let num_universes_in_response = query_response.max_universe.as_usize() + 1;
 417         for _ in num_universes_in_query..num_universes_in_response {
 418             universe_map.push(self.create_next_universe());
 419         }
 420         assert!(!universe_map.is_empty()); // always have the root universe
 421         assert_eq!(universe_map[ty::UniverseIndex::ROOT.as_usize()], ty::UniverseIndex::ROOT);
 422
 423         // Every canonical query result includes values for each of
 424         // the inputs to the query. Therefore, we begin by unifying
 425         // these values with the original inputs that were
 426         // canonicalized.
 427         let result_values = &query_response.value.var_values;
 428         assert_eq!(original_values.var_values.len(), result_values.len());
 429
 430         // Quickly try to find initial values for the canonical
 431         // variables in the result in terms of the query. We do this
 432         // by iterating down the values that the query gave to each of
 433         // the canonical inputs. If we find that one of those values
 434         // is directly equal to one of the canonical variables in the
 435         // result, then we can type the corresponding value from the
 436         // input. See the example above.
 437         let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'tcx>>> =
 438             IndexVec::from_elem_n(None, query_response.variables.len());
 439
 440         // In terms of our example above, we are iterating over pairs like:
 441         // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)]
 442         for (original_value, result_value) in iter::zip(&original_values.var_values, result_values)
 443         {
 444             match result_value.unpack() {
 445                 GenericArgKind::Type(result_value) => {
 446                     // e.g., here `result_value` might be `?0` in the example above...
 447                     if let ty::Bound(debruijn, b) = *result_value.kind() {
 448                         // ...in which case we would set `canonical_vars[0]` to `Some(?U)`.
 449
 450                         // We only allow a `ty::INNERMOST` index in substitutions.
 451                         assert_eq!(debruijn, ty::INNERMOST);
 452                         opt_values[b.var] = Some(*original_value);
 453                     }
 454                 }
 455                 GenericArgKind::Lifetime(result_value) => {
 456                     // e.g., here `result_value` might be `'?1` in the example above...
 457                     if let ty::ReLateBound(debruijn, br) = *result_value {
 458                         // ... in which case we would set `canonical_vars[0]` to `Some('static)`.
 459
 460                         // We only allow a `ty::INNERMOST` index in substitutions.
 461                         assert_eq!(debruijn, ty::INNERMOST);
 462                         opt_values[br.var] = Some(*original_value);
 463                     }
 464                 }
 465                 GenericArgKind::Const(result_value) => {
 466                     if let ty::ConstKind::Bound(debrujin, b) = result_value.kind() {
 467                         // ...in which case we would set `canonical_vars[0]` to `Some(const X)`.
 468
 469                         // We only allow a `ty::INNERMOST` index in substitutions.
 470                         assert_eq!(debrujin, ty::INNERMOST);
 471                         opt_values[b] = Some(*original_value);
 472                     }
 473                 }
 474             }
 475         }
 476
 477         // Create a result substitution: if we found a value for a
 478         // given variable in the loop above, use that. Otherwise, use
 479         // a fresh inference variable.
 480         let result_subst = CanonicalVarValues {
 481             var_values: self.tcx.mk_substs(query_response.variables.iter().enumerate().map(
 482                 |(index, info)| {
 483                     if info.is_existential() {
 484                         match opt_values[BoundVar::new(index)] {
 485                             Some(k) => k,
 486                             None => self.instantiate_canonical_var(cause.span, info, |u| {
 487                                 universe_map[u.as_usize()]
 488                             }),
 489                         }
 490                     } else {
 491                         self.instantiate_canonical_var(cause.span, info, |u| {
 492                             universe_map[u.as_usize()]
 493                         })
 494                     }
 495                 },
 496             )),
 497         };
 498
 499         let mut obligations = vec![];
 500
 501         // Carry all newly resolved opaque types to the caller's scope
 502         for &(a, b) in &query_response.value.opaque_types {
 503             let a = substitute_value(self.tcx, &result_subst, a);
 504             let b = substitute_value(self.tcx, &result_subst, b);
 505             obligations.extend(self.at(cause, param_env).eq(a, b)?.obligations);
 506         }
 507
 508         Ok(InferOk { value: result_subst, obligations })
 509     }
 510
 511     /// Given a "guess" at the values for the canonical variables in
 512     /// the input, try to unify with the *actual* values found in the
 513     /// query result. Often, but not always, this is a no-op, because
 514     /// we already found the mapping in the "guessing" step.
 515     ///
 516     /// See also: `query_response_substitution_guess`
 517     fn unify_query_response_substitution_guess<R>(
 518         &self,
 519         cause: &ObligationCause<'tcx>,
 520         param_env: ty::ParamEnv<'tcx>,
 521         original_values: &OriginalQueryValues<'tcx>,
 522         result_subst: &CanonicalVarValues<'tcx>,
 523         query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
 524     ) -> InferResult<'tcx, ()>
 525     where
 526         R: Debug + TypeFoldable<'tcx>,
 527     {
 528         // A closure that yields the result value for the given
 529         // canonical variable; this is taken from
 530         // `query_response.var_values` after applying the substitution
 531         // `result_subst`.
 532         let substituted_query_response = |index: BoundVar| -> GenericArg<'tcx> {
 533             query_response.substitute_projected(self.tcx, &result_subst, |v| v.var_values[index])
 534         };
 535
 536         // Unify the original value for each variable with the value
 537         // taken from `query_response` (after applying `result_subst`).
 538         self.unify_canonical_vars(cause, param_env, original_values, substituted_query_response)
 539     }
 540
 541     /// Converts the region constraints resulting from a query into an
 542     /// iterator of obligations.
 543     fn query_outlives_constraints_into_obligations<'a>(
 544         &'a self,
 545         cause: &'a ObligationCause<'tcx>,
 546         param_env: ty::ParamEnv<'tcx>,
 547         unsubstituted_region_constraints: &'a [QueryOutlivesConstraint<'tcx>],
 548         result_subst: &'a CanonicalVarValues<'tcx>,
 549     ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a + Captures<'tcx> {
 550         unsubstituted_region_constraints.iter().map(move |&constraint| {
 551             let predicate = substitute_value(self.tcx, result_subst, constraint);
 552             self.query_outlives_constraint_to_obligation(predicate, cause.clone(), param_env)
 553         })
 554     }
 555
 556     pub fn query_outlives_constraint_to_obligation(
 557         &self,
 558         (predicate, _): QueryOutlivesConstraint<'tcx>,
 559         cause: ObligationCause<'tcx>,
 560         param_env: ty::ParamEnv<'tcx>,
 561     ) -> Obligation<'tcx, ty::Predicate<'tcx>> {
 562         let ty::OutlivesPredicate(k1, r2) = predicate;
 563
 564         let atom = match k1.unpack() {
 565             GenericArgKind::Lifetime(r1) => {
 566                 ty::PredicateKind::Clause(ty::Clause::RegionOutlives(ty::OutlivesPredicate(r1, r2)))
 567             }
 568             GenericArgKind::Type(t1) => {
 569                 ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate(t1, r2)))
 570             }
 571             GenericArgKind::Const(..) => {
 572                 // Consts cannot outlive one another, so we don't expect to
 573                 // encounter this branch.
 574                 span_bug!(cause.span, "unexpected const outlives {:?}", predicate);
 575             }
 576         };
 577         let predicate = ty::Binder::dummy(atom);
 578
 579         Obligation::new(self.tcx, cause, param_env, predicate)
 580     }
 581
 582     /// Given two sets of values for the same set of canonical variables, unify them.
 583     /// The second set is produced lazily by supplying indices from the first set.
 584     fn unify_canonical_vars(
 585         &self,
 586         cause: &ObligationCause<'tcx>,
 587         param_env: ty::ParamEnv<'tcx>,
 588         variables1: &OriginalQueryValues<'tcx>,
 589         variables2: impl Fn(BoundVar) -> GenericArg<'tcx>,
 590     ) -> InferResult<'tcx, ()> {
 591         self.commit_if_ok(|_| {
 592             let mut obligations = vec![];
 593             for (index, value1) in variables1.var_values.iter().enumerate() {
 594                 let value2 = variables2(BoundVar::new(index));
 595
 596                 match (value1.unpack(), value2.unpack()) {
 597                     (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
 598                         obligations
 599                             .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
 600                     }
 601                     (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2))
 602                         if re1.is_erased() && re2.is_erased() =>
 603                     {
 604                         // no action needed
 605                     }
 606                     (GenericArgKind::Lifetime(v1), GenericArgKind::Lifetime(v2)) => {
 607                         obligations
 608                             .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
 609                     }
 610                     (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
 611                         let ok = self.at(cause, param_env).eq(v1, v2)?;
 612                         obligations.extend(ok.into_obligations());
 613                     }
 614                     _ => {
 615                         bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
 616                     }
 617                 }
 618             }
 619             Ok(InferOk { value: (), obligations })
 620         })
 621     }
 622 }
 623
 624 /// Given the region obligations and constraints scraped from the infcx,
 625 /// creates query region constraints.
 626 pub fn make_query_region_constraints<'tcx>(
 627     tcx: TyCtxt<'tcx>,
 628     outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>, ConstraintCategory<'tcx>)>,
 629     region_constraints: &RegionConstraintData<'tcx>,
 630 ) -> QueryRegionConstraints<'tcx> {
 631     let RegionConstraintData { constraints, verifys, givens, member_constraints } =
 632         region_constraints;
 633
 634     assert!(verifys.is_empty());
 635     assert!(givens.is_empty());
 636
 637     debug!(?constraints);
 638
 639     let outlives: Vec<_> = constraints
 640         .iter()
 641         .map(|(k, origin)| {
 642             let constraint = match *k {
 643                 // Swap regions because we are going from sub (<=) to outlives
 644                 // (>=).
 645                 Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate(
 646                     tcx.mk_region(ty::ReVar(v2)).into(),
 647                     tcx.mk_region(ty::ReVar(v1)),
 648                 ),
 649                 Constraint::VarSubReg(v1, r2) => {
 650                     ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1)))
 651                 }
 652                 Constraint::RegSubVar(r1, v2) => {
 653                     ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1)
 654                 }
 655                 Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1),
 656             };
 657             (constraint, origin.to_constraint_category())
 658         })
 659         .chain(outlives_obligations.map(|(ty, r, constraint_category)| {
 660             (ty::OutlivesPredicate(ty.into(), r), constraint_category)
 661         }))
 662         .collect();
 663
 664     QueryRegionConstraints { outlives, member_constraints: member_constraints.clone() }
 665 }
 666
 667 struct QueryTypeRelatingDelegate<'a, 'tcx> {
 668     infcx: &'a InferCtxt<'tcx>,
 669     obligations: &'a mut Vec<PredicateObligation<'tcx>>,
 670     param_env: ty::ParamEnv<'tcx>,
 671     cause: &'a ObligationCause<'tcx>,
 672 }
 673
 674 impl<'tcx> TypeRelatingDelegate<'tcx> for QueryTypeRelatingDelegate<'_, 'tcx> {
 675     fn span(&self) -> Span {
 676         self.cause.span
 677     }
 678
 679     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 680         self.param_env
 681     }
 682
 683     fn create_next_universe(&mut self) -> ty::UniverseIndex {
 684         self.infcx.create_next_universe()
 685     }
 686
 687     fn next_existential_region_var(&mut self, from_forall: bool) -> ty::Region<'tcx> {
 688         let origin = NllRegionVariableOrigin::Existential { from_forall };
 689         self.infcx.next_nll_region_var(origin)
 690     }
 691
 692     fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> {
 693         self.infcx.tcx.mk_region(ty::RePlaceholder(placeholder))
 694     }
 695
 696     fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> {
 697         self.infcx.next_nll_region_var_in_universe(
 698             NllRegionVariableOrigin::Existential { from_forall: false },
 699             universe,
 700         )
 701     }
 702
 703     fn push_outlives(
 704         &mut self,
 705         sup: ty::Region<'tcx>,
 706         sub: ty::Region<'tcx>,
 707         _info: ty::VarianceDiagInfo<'tcx>,
 708     ) {
 709         self.obligations.push(Obligation {
 710             cause: self.cause.clone(),
 711             param_env: self.param_env,
 712             predicate: ty::Binder::dummy(ty::PredicateKind::Clause(ty::Clause::RegionOutlives(
 713                 ty::OutlivesPredicate(sup, sub),
 714             )))
 715             .to_predicate(self.infcx.tcx),
 716             recursion_depth: 0,
 717         });
 718     }
 719
 720     fn normalization() -> NormalizationStrategy {
 721         NormalizationStrategy::Eager
 722     }
 723
 724     fn forbid_inference_vars() -> bool {
 725         true
 726     }
 727
 728     fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
 729         self.obligations.extend(obligations);
 730     }
 731 }