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                 // Evaluation will discard candidates using the leak check.
 324                 // This means we need to pass it the bound version of our
 325                 // predicate.
 326                 ty::PredicateKind::Trait(trait_ref, _constness) => {
 327                     let trait_obligation = obligation.with(Binder::bind(*trait_ref));
 328
 329                     self.process_trait_obligation(
 330                         obligation,
 331                         trait_obligation,
 332                         &mut pending_obligation.stalled_on,
 333                     )
 334                 }
 335                 ty::PredicateKind::Projection(projection) => {
 336                     let project_obligation = obligation.with(Binder::bind(*projection));
 337
 338                     self.process_projection_obligation(
 339                         project_obligation,
 340                         &mut pending_obligation.stalled_on,
 341                     )
 342                 }
 343                 ty::PredicateKind::RegionOutlives(_)
 344                 | ty::PredicateKind::TypeOutlives(_)
 345                 | ty::PredicateKind::WellFormed(_)
 346                 | ty::PredicateKind::ObjectSafe(_)
 347                 | ty::PredicateKind::ClosureKind(..)
 348                 | ty::PredicateKind::Subtype(_)
 349                 | ty::PredicateKind::ConstEvaluatable(..)
 350                 | ty::PredicateKind::ConstEquate(..)
 351                 | ty::PredicateKind::ForAll(_) => {
 352                     let (pred, _) = infcx.replace_bound_vars_with_placeholders(binder);
 353                     ProcessResult::Changed(mk_pending(vec![obligation.with(pred)]))
 354                 }
 355             },
 356             ty::PredicateKind::Trait(ref data, _) => {
 357                 let trait_obligation = obligation.with(Binder::dummy(*data));
 358
 359                 self.process_trait_obligation(
 360                     obligation,
 361                     trait_obligation,
 362                     &mut pending_obligation.stalled_on,
 363                 )
 364             }
 365
 366             &ty::PredicateKind::RegionOutlives(data) => {
 367                 match infcx.region_outlives_predicate(&obligation.cause, Binder::dummy(data)) {
 368                     Ok(()) => ProcessResult::Changed(vec![]),
 369                     Err(_) => ProcessResult::Error(CodeSelectionError(Unimplemented)),
 370                 }
 371             }
 372
 373             ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(t_a, r_b)) => {
 374                 if self.register_region_obligations {
 375                     self.selcx.infcx().register_region_obligation_with_cause(
 376                         t_a,
 377                         r_b,
 378                         &obligation.cause,
 379                     );
 380                 }
 381                 ProcessResult::Changed(vec![])
 382             }
 383
 384             ty::PredicateKind::Projection(ref data) => {
 385                 let project_obligation = obligation.with(Binder::dummy(*data));
 386
 387                 self.process_projection_obligation(
 388                     project_obligation,
 389                     &mut pending_obligation.stalled_on,
 390                 )
 391             }
 392
 393             &ty::PredicateKind::ObjectSafe(trait_def_id) => {
 394                 if !self.selcx.tcx().is_object_safe(trait_def_id) {
 395                     ProcessResult::Error(CodeSelectionError(Unimplemented))
 396                 } else {
 397                     ProcessResult::Changed(vec![])
 398                 }
 399             }
 400
 401             &ty::PredicateKind::ClosureKind(_, closure_substs, kind) => {
 402                 match self.selcx.infcx().closure_kind(closure_substs) {
 403                     Some(closure_kind) => {
 404                         if closure_kind.extends(kind) {
 405                             ProcessResult::Changed(vec![])
 406                         } else {
 407                             ProcessResult::Error(CodeSelectionError(Unimplemented))
 408                         }
 409                     }
 410                     None => ProcessResult::Unchanged,
 411                 }
 412             }
 413
 414             &ty::PredicateKind::WellFormed(arg) => {
 415                 match wf::obligations(
 416                     self.selcx.infcx(),
 417                     obligation.param_env,
 418                     obligation.cause.body_id,
 419                     arg,
 420                     obligation.cause.span,
 421                 ) {
 422                     None => {
 423                         pending_obligation.stalled_on =
 424                             vec![TyOrConstInferVar::maybe_from_generic_arg(arg).unwrap()];
 425                         ProcessResult::Unchanged
 426                     }
 427                     Some(os) => ProcessResult::Changed(mk_pending(os)),
 428                 }
 429             }
 430
 431             &ty::PredicateKind::Subtype(subtype) => {
 432                 match self.selcx.infcx().subtype_predicate(
 433                     &obligation.cause,
 434                     obligation.param_env,
 435                     Binder::dummy(subtype),
 436                 ) {
 437                     None => {
 438                         // None means that both are unresolved.
 439                         pending_obligation.stalled_on = vec![
 440                             TyOrConstInferVar::maybe_from_ty(subtype.a).unwrap(),
 441                             TyOrConstInferVar::maybe_from_ty(subtype.b).unwrap(),
 442                         ];
 443                         ProcessResult::Unchanged
 444                     }
 445                     Some(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)),
 446                     Some(Err(err)) => {
 447                         let expected_found =
 448                             ExpectedFound::new(subtype.a_is_expected, subtype.a, subtype.b);
 449                         ProcessResult::Error(FulfillmentErrorCode::CodeSubtypeError(
 450                             expected_found,
 451                             err,
 452                         ))
 453                     }
 454                 }
 455             }
 456
 457             &ty::PredicateKind::ConstEvaluatable(def_id, substs) => {
 458                 match self.selcx.infcx().const_eval_resolve(
 459                     obligation.param_env,
 460                     def_id,
 461                     substs,
 462                     None,
 463                     Some(obligation.cause.span),
 464                 ) {
 465                     Ok(_) => ProcessResult::Changed(vec![]),
 466                     Err(err) => ProcessResult::Error(CodeSelectionError(ConstEvalFailure(err))),
 467                 }
 468             }
 469
 470             ty::PredicateKind::ConstEquate(c1, c2) => {
 471                 debug!("equating consts: c1={:?} c2={:?}", c1, c2);
 472
 473                 let stalled_on = &mut pending_obligation.stalled_on;
 474
 475                 let mut evaluate = |c: &'tcx Const<'tcx>| {
 476                     if let ty::ConstKind::Unevaluated(def, substs, promoted) = c.val {
 477                         match self.selcx.infcx().const_eval_resolve(
 478                             obligation.param_env,
 479                             def,
 480                             substs,
 481                             promoted,
 482                             Some(obligation.cause.span),
 483                         ) {
 484                             Ok(val) => Ok(Const::from_value(self.selcx.tcx(), val, c.ty)),
 485                             Err(ErrorHandled::TooGeneric) => {
 486                                 stalled_on.append(
 487                                     &mut substs
 488                                         .types()
 489                                         .filter_map(|ty| TyOrConstInferVar::maybe_from_ty(ty))
 490                                         .collect(),
 491                                 );
 492                                 Err(ErrorHandled::TooGeneric)
 493                             }
 494                             Err(err) => Err(err),
 495                         }
 496                     } else {
 497                         Ok(c)
 498                     }
 499                 };
 500
 501                 match (evaluate(c1), evaluate(c2)) {
 502                     (Ok(c1), Ok(c2)) => {
 503                         match self
 504                             .selcx
 505                             .infcx()
 506                             .at(&obligation.cause, obligation.param_env)
 507                             .eq(c1, c2)
 508                         {
 509                             Ok(_) => ProcessResult::Changed(vec![]),
 510                             Err(err) => {
 511                                 ProcessResult::Error(FulfillmentErrorCode::CodeConstEquateError(
 512                                     ExpectedFound::new(true, c1, c2),
 513                                     err,
 514                                 ))
 515                             }
 516                         }
 517                     }
 518                     (Err(ErrorHandled::Reported(ErrorReported)), _)
 519                     | (_, Err(ErrorHandled::Reported(ErrorReported))) => ProcessResult::Error(
 520                         CodeSelectionError(ConstEvalFailure(ErrorHandled::Reported(ErrorReported))),
 521                     ),
 522                     (Err(ErrorHandled::Linted), _) | (_, Err(ErrorHandled::Linted)) => span_bug!(
 523                         obligation.cause.span(self.selcx.tcx()),
 524                         "ConstEquate: const_eval_resolve returned an unexpected error"
 525                     ),
 526                     (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => {
 527                         ProcessResult::Unchanged
 528                     }
 529                 }
 530             }
 531         }
 532     }
 533
 534     fn process_backedge<'c, I>(
 535         &mut self,
 536         cycle: I,
 537         _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>,
 538     ) where
 539         I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>,
 540     {
 541         if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
 542             debug!("process_child_obligations: coinductive match");
 543         } else {
 544             let cycle: Vec<_> = cycle.map(|c| c.obligation.clone()).collect();
 545             self.selcx.infcx().report_overflow_error_cycle(&cycle);
 546         }
 547     }
 548 }
 549
 550 impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> {
 551     fn process_trait_obligation(
 552         &mut self,
 553         obligation: &PredicateObligation<'tcx>,
 554         trait_obligation: PolyTraitObligation<'tcx>,
 555         stalled_on: &mut Vec<TyOrConstInferVar<'tcx>>,
 556     ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
 557         let infcx = self.selcx.infcx();
 558         if obligation.predicate.is_global() {
 559             // no type variables present, can use evaluation for better caching.
 560             // FIXME: consider caching errors too.
 561             if infcx.predicate_must_hold_considering_regions(obligation) {
 562                 debug!(
 563                     "selecting trait `{:?}` at depth {} evaluated to holds",
 564                     obligation.predicate, obligation.recursion_depth
 565                 );
 566                 return ProcessResult::Changed(vec![]);
 567             }
 568         }
 569
 570         match self.selcx.select(&trait_obligation) {
 571             Ok(Some(impl_source)) => {
 572                 debug!(
 573                     "selecting trait `{:?}` at depth {} yielded Ok(Some)",
 574                     trait_obligation.predicate, obligation.recursion_depth
 575                 );
 576                 ProcessResult::Changed(mk_pending(impl_source.nested_obligations()))
 577             }
 578             Ok(None) => {
 579                 debug!(
 580                     "selecting trait `{:?}` at depth {} yielded Ok(None)",
 581                     trait_obligation.predicate, obligation.recursion_depth
 582                 );
 583
 584                 // This is a bit subtle: for the most part, the
 585                 // only reason we can fail to make progress on
 586                 // trait selection is because we don't have enough
 587                 // information about the types in the trait.
 588                 *stalled_on = trait_ref_infer_vars(
 589                     self.selcx,
 590                     trait_obligation.predicate.map_bound(|pred| pred.trait_ref),
 591                 );
 592
 593                 debug!(
 594                     "process_predicate: pending obligation {:?} now stalled on {:?}",
 595                     infcx.resolve_vars_if_possible(obligation),
 596                     stalled_on
 597                 );
 598
 599                 ProcessResult::Unchanged
 600             }
 601             Err(selection_err) => {
 602                 info!(
 603                     "selecting trait `{:?}` at depth {} yielded Err",
 604                     trait_obligation.predicate, obligation.recursion_depth
 605                 );
 606
 607                 ProcessResult::Error(CodeSelectionError(selection_err))
 608             }
 609         }
 610     }
 611
 612     fn process_projection_obligation(
 613         &mut self,
 614         project_obligation: PolyProjectionObligation<'tcx>,
 615         stalled_on: &mut Vec<TyOrConstInferVar<'tcx>>,
 616     ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
 617         match project::poly_project_and_unify_type(self.selcx, &project_obligation) {
 618             Ok(None) => {
 619                 *stalled_on = trait_ref_infer_vars(
 620                     self.selcx,
 621                     project_obligation.predicate.to_poly_trait_ref(self.selcx.tcx()),
 622                 );
 623                 ProcessResult::Unchanged
 624             }
 625             Ok(Some(os)) => ProcessResult::Changed(mk_pending(os)),
 626             Err(e) => ProcessResult::Error(CodeProjectionError(e)),
 627         }
 628     }
 629 }
 630
 631 /// Returns the set of inference variables contained in a trait ref.
 632 fn trait_ref_infer_vars<'a, 'tcx>(
 633     selcx: &mut SelectionContext<'a, 'tcx>,
 634     trait_ref: ty::PolyTraitRef<'tcx>,
 635 ) -> Vec<TyOrConstInferVar<'tcx>> {
 636     selcx
 637         .infcx()
 638         .resolve_vars_if_possible(&trait_ref)
 639         .skip_binder()
 640         .substs
 641         .iter()
 642         // FIXME(eddyb) try using `skip_current_subtree` to skip everything that
 643         // doesn't contain inference variables, not just the outermost level.
 644         .filter(|arg| arg.has_infer_types_or_consts())
 645         .flat_map(|arg| arg.walk())
 646         .filter_map(TyOrConstInferVar::maybe_from_generic_arg)
 647         .collect()
 648 }
 649
 650 fn to_fulfillment_error<'tcx>(
 651     error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>,
 652 ) -> FulfillmentError<'tcx> {
 653     let obligation = error.backtrace.into_iter().next().unwrap().obligation;
 654     FulfillmentError::new(obligation, error.error)
 655 }