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