src/librustc/traits/fulfill.rs

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