src/librustc/traits/fulfill.rs

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