src/librustc_infer/traits/fulfill.rs

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