src/librustc_trait_selection/traits/fulfill.rs

   1 use crate::infer::{InferCtxt, TyOrConstInferVar};
   2 use rustc_data_structures::obligation_forest::ProcessResult;
   3 use rustc_data_structures::obligation_forest::{DoCompleted, Error, ForestObligation};
   4 use rustc_data_structures::obligation_forest::{ObligationForest, ObligationProcessor};
   5 use rustc_infer::traits::{TraitEngine, TraitEngineExt as _};
   6 use rustc_middle::ty::error::ExpectedFound;
   7 use rustc_middle::ty::{self, ToPolyTraitRef, Ty, TypeFoldable};
   8 use std::marker::PhantomData;
   9
  10 use super::project;
  11 use super::select::SelectionContext;
  12 use super::wf;
  13 use super::CodeAmbiguity;
  14 use super::CodeProjectionError;
  15 use super::CodeSelectionError;
  16 use super::{ConstEvalFailure, Unimplemented};
  17 use super::{FulfillmentError, FulfillmentErrorCode};
  18 use super::{ObligationCause, PredicateObligation};
  19
  20 use crate::traits::error_reporting::InferCtxtExt as _;
  21 use crate::traits::query::evaluate_obligation::InferCtxtExt as _;
  22
  23 impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> {
  24     /// Note that we include both the `ParamEnv` and the `Predicate`,
  25     /// as the `ParamEnv` can influence whether fulfillment succeeds
  26     /// or fails.
  27     type CacheKey = ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>;
  28
  29     fn as_cache_key(&self) -> Self::CacheKey {
  30         self.obligation.param_env.and(self.obligation.predicate)
  31     }
  32 }
  33
  34 /// The fulfillment context is used to drive trait resolution. It
  35 /// consists of a list of obligations that must be (eventually)
  36 /// satisfied. The job is to track which are satisfied, which yielded
  37 /// errors, and which are still pending. At any point, users can call
  38 /// `select_where_possible`, and the fulfillment context will try to do
  39 /// selection, retaining only those obligations that remain
  40 /// ambiguous. This may be helpful in pushing type inference
  41 /// along. Once all type inference constraints have been generated, the
  42 /// method `select_all_or_error` can be used to report any remaining
  43 /// ambiguous cases as errors.
  44 pub struct FulfillmentContext<'tcx> {
  45     // A list of all obligations that have been registered with this
  46     // fulfillment context.
  47     predicates: ObligationForest<PendingPredicateObligation<'tcx>>,
  48     // Should this fulfillment context register type-lives-for-region
  49     // obligations on its parent infcx? In some cases, region
  50     // obligations are either already known to hold (normalization) or
  51     // hopefully verifed elsewhere (type-impls-bound), and therefore
  52     // should not be checked.
  53     //
  54     // Note that if we are normalizing a type that we already
  55     // know is well-formed, there should be no harm setting this
  56     // to true - all the region variables should be determinable
  57     // using the RFC 447 rules, which don't depend on
  58     // type-lives-for-region constraints, and because the type
  59     // is well-formed, the constraints should hold.
  60     register_region_obligations: bool,
  61     // Is it OK to register obligations into this infcx inside
  62     // an infcx snapshot?
  63     //
  64     // The "primary fulfillment" in many cases in typeck lives
  65     // outside of any snapshot, so any use of it inside a snapshot
  66     // will lead to trouble and therefore is checked against, but
  67     // other fulfillment contexts sometimes do live inside of
  68     // a snapshot (they don't *straddle* a snapshot, so there
  69     // is no trouble there).
  70     usable_in_snapshot: bool,
  71 }
  72
  73 #[derive(Clone, Debug)]
  74 pub struct PendingPredicateObligation<'tcx> {
  75     pub obligation: PredicateObligation<'tcx>,
  76     // FIXME(eddyb) look into whether this could be a `SmallVec`.
  77     // Judging by the comment in `process_obligation`, the 1-element case
  78     // is common so this could be a `SmallVec<[TyOrConstInferVar<'tcx>; 1]>`.
  79     pub stalled_on: Vec<TyOrConstInferVar<'tcx>>,
  80 }
  81
  82 // `PendingPredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
  83 #[cfg(target_arch = "x86_64")]
  84 static_assert_size!(PendingPredicateObligation<'_>, 136);
  85
  86 impl<'a, 'tcx> FulfillmentContext<'tcx> {
  87     /// Creates a new fulfillment context.
  88     pub fn new() -> FulfillmentContext<'tcx> {
  89         FulfillmentContext {
  90             predicates: ObligationForest::new(),
  91             register_region_obligations: true,
  92             usable_in_snapshot: false,
  93         }
  94     }
  95
  96     pub fn new_in_snapshot() -> FulfillmentContext<'tcx> {
  97         FulfillmentContext {
  98             predicates: ObligationForest::new(),
  99             register_region_obligations: true,
 100             usable_in_snapshot: true,
 101         }
 102     }
 103
 104     pub fn new_ignoring_regions() -> FulfillmentContext<'tcx> {
 105         FulfillmentContext {
 106             predicates: ObligationForest::new(),
 107             register_region_obligations: false,
 108             usable_in_snapshot: false,
 109         }
 110     }
 111
 112     /// Attempts to select obligations using `selcx`.
 113     fn select(
 114         &mut self,
 115         selcx: &mut SelectionContext<'a, 'tcx>,
 116     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
 117         debug!("select(obligation-forest-size={})", self.predicates.len());
 118
 119         let mut errors = Vec::new();
 120
 121         loop {
 122             debug!("select: starting another iteration");
 123
 124             // Process pending obligations.
 125             let outcome = self.predicates.process_obligations(
 126                 &mut FulfillProcessor {
 127                     selcx,
 128                     register_region_obligations: self.register_region_obligations,
 129                 },
 130                 DoCompleted::No,
 131             );
 132             debug!("select: outcome={:#?}", outcome);
 133
 134             // FIXME: if we kept the original cache key, we could mark projection
 135             // obligations as complete for the projection cache here.
 136
 137             errors.extend(outcome.errors.into_iter().map(to_fulfillment_error));
 138
 139             // If nothing new was added, no need to keep looping.
 140             if outcome.stalled {
 141                 break;
 142             }
 143         }
 144
 145         debug!(
 146             "select({} predicates remaining, {} errors) done",
 147             self.predicates.len(),
 148             errors.len()
 149         );
 150
 151         if errors.is_empty() { Ok(()) } else { Err(errors) }
 152     }
 153 }
 154
 155 impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> {
 156     /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by
 157     /// creating a fresh type variable `$0` as well as a projection
 158     /// predicate `<SomeType as SomeTrait>::X == $0`. When the
 159     /// inference engine runs, it will attempt to find an impl of
 160     /// `SomeTrait` or a where-clause that lets us unify `$0` with
 161     /// something concrete. If this fails, we'll unify `$0` with
 162     /// `projection_ty` again.
 163     fn normalize_projection_type(
 164         &mut self,
 165         infcx: &InferCtxt<'_, 'tcx>,
 166         param_env: ty::ParamEnv<'tcx>,
 167         projection_ty: ty::ProjectionTy<'tcx>,
 168         cause: ObligationCause<'tcx>,
 169     ) -> Ty<'tcx> {
 170         debug!("normalize_projection_type(projection_ty={:?})", projection_ty);
 171
 172         debug_assert!(!projection_ty.has_escaping_bound_vars());
 173
 174         // FIXME(#20304) -- cache
 175
 176         let mut selcx = SelectionContext::new(infcx);
 177         let mut obligations = vec![];
 178         let normalized_ty = project::normalize_projection_type(
 179             &mut selcx,
 180             param_env,
 181             projection_ty,
 182             cause,
 183             0,
 184             &mut obligations,
 185         );
 186         self.register_predicate_obligations(infcx, obligations);
 187
 188         debug!("normalize_projection_type: result={:?}", normalized_ty);
 189
 190         normalized_ty
 191     }
 192
 193     fn register_predicate_obligation(
 194         &mut self,
 195         infcx: &InferCtxt<'_, 'tcx>,
 196         obligation: PredicateObligation<'tcx>,
 197     ) {
 198         // this helps to reduce duplicate errors, as well as making
 199         // debug output much nicer to read and so on.
 200         let obligation = infcx.resolve_vars_if_possible(&obligation);
 201
 202         debug!("register_predicate_obligation(obligation={:?})", obligation);
 203
 204         assert!(!infcx.is_in_snapshot() || self.usable_in_snapshot);
 205
 206         self.predicates
 207             .register_obligation(PendingPredicateObligation { obligation, stalled_on: vec![] });
 208     }
 209
 210     fn select_all_or_error(
 211         &mut self,
 212         infcx: &InferCtxt<'_, 'tcx>,
 213     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
 214         self.select_where_possible(infcx)?;
 215
 216         let errors: Vec<_> = self
 217             .predicates
 218             .to_errors(CodeAmbiguity)
 219             .into_iter()
 220             .map(to_fulfillment_error)
 221             .collect();
 222         if errors.is_empty() { Ok(()) } else { Err(errors) }
 223     }
 224
 225     fn select_where_possible(
 226         &mut self,
 227         infcx: &InferCtxt<'_, 'tcx>,
 228     ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
 229         let mut selcx = SelectionContext::new(infcx);
 230         self.select(&mut selcx)
 231     }
 232
 233     fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
 234         self.predicates.map_pending_obligations(|o| o.obligation.clone())
 235     }
 236 }
 237
 238 struct FulfillProcessor<'a, 'b, 'tcx> {
 239     selcx: &'a mut SelectionContext<'b, 'tcx>,
 240     register_region_obligations: bool,
 241 }
 242
 243 fn mk_pending(os: Vec<PredicateObligation<'tcx>>) -> Vec<PendingPredicateObligation<'tcx>> {
 244     os.into_iter()
 245         .map(|o| PendingPredicateObligation { obligation: o, stalled_on: vec![] })
 246         .collect()
 247 }
 248
 249 impl<'a, 'b, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'tcx> {
 250     type Obligation = PendingPredicateObligation<'tcx>;
 251     type Error = FulfillmentErrorCode<'tcx>;
 252
 253     /// Processes a predicate obligation and returns either:
 254     /// - `Changed(v)` if the predicate is true, presuming that `v` are also true
 255     /// - `Unchanged` if we don't have enough info to be sure
 256     /// - `Error(e)` if the predicate does not hold
 257     ///
 258     /// This is always inlined, despite its size, because it has a single
 259     /// callsite and it is called *very* frequently.
 260     #[inline(always)]
 261     fn process_obligation(
 262         &mut self,
 263         pending_obligation: &mut Self::Obligation,
 264     ) -> ProcessResult<Self::Obligation, Self::Error> {
 265         // If we were stalled on some unresolved variables, first check whether
 266         // any of them have been resolved; if not, don't bother doing more work
 267         // yet.
 268         let change = match pending_obligation.stalled_on.len() {
 269             // Match arms are in order of frequency, which matters because this
 270             // code is so hot. 1 and 0 dominate; 2+ is fairly rare.
 271             1 => {
 272                 let infer_var = pending_obligation.stalled_on[0];
 273                 self.selcx.infcx().ty_or_const_infer_var_changed(infer_var)
 274             }
 275             0 => {
 276                 // In this case we haven't changed, but wish to make a change.
 277                 true
 278             }
 279             _ => {
 280                 // This `for` loop was once a call to `all()`, but this lower-level
 281                 // form was a perf win. See #64545 for details.
 282                 (|| {
 283                     for &infer_var in &pending_obligation.stalled_on {
 284                         if self.selcx.infcx().ty_or_const_infer_var_changed(infer_var) {
 285                             return true;
 286                         }
 287                     }
 288                     false
 289                 })()
 290             }
 291         };
 292
 293         if !change {
 294             debug!(
 295                 "process_predicate: pending obligation {:?} still stalled on {:?}",
 296                 self.selcx.infcx().resolve_vars_if_possible(&pending_obligation.obligation),
 297                 pending_obligation.stalled_on
 298             );
 299             return ProcessResult::Unchanged;
 300         }
 301
 302         // This part of the code is much colder.
 303
 304         pending_obligation.stalled_on.truncate(0);
 305
 306         let obligation = &mut pending_obligation.obligation;
 307
 308         if obligation.predicate.has_infer_types_or_consts() {
 309             obligation.predicate =
 310                 self.selcx.infcx().resolve_vars_if_possible(&obligation.predicate);
 311         }
 312
 313         debug!("process_obligation: obligation = {:?} cause = {:?}", obligation, obligation.cause);
 314
 315         match obligation.predicate {
 316             ty::Predicate::Trait(ref data, _) => {
 317                 let trait_obligation = obligation.with(*data);
 318
 319                 if data.is_global() {
 320                     // no type variables present, can use evaluation for better caching.
 321                     // FIXME: consider caching errors too.
 322                     if self.selcx.infcx().predicate_must_hold_considering_regions(&obligation) {
 323                         debug!(
 324                             "selecting trait `{:?}` at depth {} evaluated to holds",
 325                             data, obligation.recursion_depth
 326                         );
 327                         return ProcessResult::Changed(vec![]);
 328                     }
 329                 }
 330
 331                 match self.selcx.select(&trait_obligation) {
 332                     Ok(Some(vtable)) => {
 333                         debug!(
 334                             "selecting trait `{:?}` at depth {} yielded Ok(Some)",
 335                             data, obligation.recursion_depth
 336                         );
 337                         ProcessResult::Changed(mk_pending(vtable.nested_obligations()))
 338                     }
 339                     Ok(None) => {
 340                         debug!(
 341                             "selecting trait `{:?}` at depth {} yielded Ok(None)",
 342                             data, obligation.recursion_depth
 343                         );
 344
 345                         // This is a bit subtle: for the most part, the
 346                         // only reason we can fail to make progress on
 347                         // trait selection is because we don't have enough
 348                         // information about the types in the trait.
 349                         pending_obligation.stalled_on =
 350                             trait_ref_type_vars(self.selcx, data.to_poly_trait_ref());
 351
 352                         debug!(
 353                             "process_predicate: pending obligation {:?} now stalled on {:?}",
 354                             self.selcx.infcx().resolve_vars_if_possible(obligation),
 355                             pending_obligation.stalled_on
 356                         );
 357
 358                         ProcessResult::Unchanged
 359                     }
 360                     Err(selection_err) => {
 361                         info!(
 362                             "selecting trait `{:?}` at depth {} yielded Err",
 363                             data, obligation.recursion_depth
 364                         );
 365
 366                         ProcessResult::Error(CodeSelectionError(selection_err))
 367                     }
 368                 }
 369             }
 370
 371             ty::Predicate::RegionOutlives(ref binder) => {
 372                 match self.selcx.infcx().region_outlives_predicate(&obligation.cause, binder) {
 373                     Ok(()) => ProcessResult::Changed(vec![]),
 374                     Err(_) => ProcessResult::Error(CodeSelectionError(Unimplemented)),
 375                 }
 376             }
 377
 378             ty::Predicate::TypeOutlives(ref binder) => {
 379                 // Check if there are higher-ranked vars.
 380                 match binder.no_bound_vars() {
 381                     // If there are, inspect the underlying type further.
 382                     None => {
 383                         // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`.
 384                         let binder = binder.map_bound_ref(|pred| pred.0);
 385
 386                         // Check if the type has any bound vars.
 387                         match binder.no_bound_vars() {
 388                             // If so, this obligation is an error (for now). Eventually we should be
 389                             // able to support additional cases here, like `for<'a> &'a str: 'a`.
 390                             // NOTE: this is duplicate-implemented between here and fulfillment.
 391                             None => ProcessResult::Error(CodeSelectionError(Unimplemented)),
 392                             // Otherwise, we have something of the form
 393                             // `for<'a> T: 'a where 'a not in T`, which we can treat as
 394                             // `T: 'static`.
 395                             Some(t_a) => {
 396                                 let r_static = self.selcx.tcx().lifetimes.re_static;
 397                                 if self.register_region_obligations {
 398                                     self.selcx.infcx().register_region_obligation_with_cause(
 399                                         t_a,
 400                                         r_static,
 401                                         &obligation.cause,
 402                                     );
 403                                 }
 404                                 ProcessResult::Changed(vec![])
 405                             }
 406                         }
 407                     }
 408                     // If there aren't, register the obligation.
 409                     Some(ty::OutlivesPredicate(t_a, r_b)) => {
 410                         if self.register_region_obligations {
 411                             self.selcx.infcx().register_region_obligation_with_cause(
 412                                 t_a,
 413                                 r_b,
 414                                 &obligation.cause,
 415                             );
 416                         }
 417                         ProcessResult::Changed(vec![])
 418                     }
 419                 }
 420             }
 421
 422             ty::Predicate::Projection(ref data) => {
 423                 let project_obligation = obligation.with(*data);
 424                 match project::poly_project_and_unify_type(self.selcx, &project_obligation) {
 425                     Ok(None) => {
 426                         let tcx = self.selcx.tcx();
 427                         pending_obligation.stalled_on =
 428                             trait_ref_type_vars(self.selcx, data.to_poly_trait_ref(tcx));
 429                         ProcessResult::Unchanged
 430                     }
 431                     Ok(Some(os)) => ProcessResult::Changed(mk_pending(os)),
 432                     Err(e) => ProcessResult::Error(CodeProjectionError(e)),
 433                 }
 434             }
 435
 436             ty::Predicate::ObjectSafe(trait_def_id) => {
 437                 if !self.selcx.tcx().is_object_safe(trait_def_id) {
 438                     ProcessResult::Error(CodeSelectionError(Unimplemented))
 439                 } else {
 440                     ProcessResult::Changed(vec![])
 441                 }
 442             }
 443
 444             ty::Predicate::ClosureKind(_, closure_substs, kind) => {
 445                 match self.selcx.infcx().closure_kind(closure_substs) {
 446                     Some(closure_kind) => {
 447                         if closure_kind.extends(kind) {
 448                             ProcessResult::Changed(vec![])
 449                         } else {
 450                             ProcessResult::Error(CodeSelectionError(Unimplemented))
 451                         }
 452                     }
 453                     None => ProcessResult::Unchanged,
 454                 }
 455             }
 456
 457             ty::Predicate::WellFormed(ty) => {
 458                 match wf::obligations(
 459                     self.selcx.infcx(),
 460                     obligation.param_env,
 461                     obligation.cause.body_id,
 462                     ty,
 463                     obligation.cause.span,
 464                 ) {
 465                     None => {
 466                         pending_obligation.stalled_on =
 467                             vec![TyOrConstInferVar::maybe_from_ty(ty).unwrap()];
 468                         ProcessResult::Unchanged
 469                     }
 470                     Some(os) => ProcessResult::Changed(mk_pending(os)),
 471                 }
 472             }
 473
 474             ty::Predicate::Subtype(ref subtype) => {
 475                 match self.selcx.infcx().subtype_predicate(
 476                     &obligation.cause,
 477                     obligation.param_env,
 478                     subtype,
 479                 ) {
 480                     None => {
 481                         // None means that both are unresolved.
 482                         pending_obligation.stalled_on = vec![
 483                             TyOrConstInferVar::maybe_from_ty(subtype.skip_binder().a).unwrap(),
 484                             TyOrConstInferVar::maybe_from_ty(subtype.skip_binder().b).unwrap(),
 485                         ];
 486                         ProcessResult::Unchanged
 487                     }
 488                     Some(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)),
 489                     Some(Err(err)) => {
 490                         let expected_found = ExpectedFound::new(
 491                             subtype.skip_binder().a_is_expected,
 492                             subtype.skip_binder().a,
 493                             subtype.skip_binder().b,
 494                         );
 495                         ProcessResult::Error(FulfillmentErrorCode::CodeSubtypeError(
 496                             expected_found,
 497                             err,
 498                         ))
 499                     }
 500                 }
 501             }
 502
 503             ty::Predicate::ConstEvaluatable(def_id, substs) => {
 504                 match self.selcx.infcx().const_eval_resolve(
 505                     obligation.param_env,
 506                     def_id,
 507                     substs,
 508                     None,
 509                     Some(obligation.cause.span),
 510                 ) {
 511                     Ok(_) => ProcessResult::Changed(vec![]),
 512                     Err(err) => ProcessResult::Error(CodeSelectionError(ConstEvalFailure(err))),
 513                 }
 514             }
 515         }
 516     }
 517
 518     fn process_backedge<'c, I>(
 519         &mut self,
 520         cycle: I,
 521         _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>,
 522     ) where
 523         I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>,
 524     {
 525         if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
 526             debug!("process_child_obligations: coinductive match");
 527         } else {
 528             let cycle: Vec<_> = cycle.map(|c| c.obligation.clone()).collect();
 529             self.selcx.infcx().report_overflow_error_cycle(&cycle);
 530         }
 531     }
 532 }
 533
 534 /// Returns the set of type inference variables contained in a trait ref.
 535 fn trait_ref_type_vars<'a, 'tcx>(
 536     selcx: &mut SelectionContext<'a, 'tcx>,
 537     trait_ref: ty::PolyTraitRef<'tcx>,
 538 ) -> Vec<TyOrConstInferVar<'tcx>> {
 539     selcx
 540         .infcx()
 541         .resolve_vars_if_possible(&trait_ref)
 542         .skip_binder() // ok b/c this check doesn't care about regions
 543         .substs
 544         .iter()
 545         // FIXME(eddyb) try using `skip_current_subtree` to skip everything that
 546         // doesn't contain inference variables, not just the outermost level.
 547         .filter(|arg| arg.has_infer_types_or_consts())
 548         .flat_map(|arg| arg.walk())
 549         .filter_map(TyOrConstInferVar::maybe_from_generic_arg)
 550         .collect()
 551 }
 552
 553 fn to_fulfillment_error<'tcx>(
 554     error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>,
 555 ) -> FulfillmentError<'tcx> {
 556     let obligation = error.backtrace.into_iter().next().unwrap().obligation;
 557     FulfillmentError::new(obligation, error.error)
 558 }