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