src/librustc/traits/fulfill.rs

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