src/librustc/middle/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 middle::infer::InferCtxt;
  12 use middle::ty::{self, RegionEscape, Ty};
  13
  14 use std::collections::HashSet;
  15 use std::fmt;
  16 use syntax::ast;
  17 use util::common::ErrorReported;
  18 use util::nodemap::NodeMap;
  19
  20 use super::CodeAmbiguity;
  21 use super::CodeProjectionError;
  22 use super::CodeSelectionError;
  23 use super::FulfillmentError;
  24 use super::ObligationCause;
  25 use super::PredicateObligation;
  26 use super::project;
  27 use super::select::SelectionContext;
  28 use super::Unimplemented;
  29 use super::util::predicate_for_builtin_bound;
  30
  31 pub struct FulfilledPredicates<'tcx> {
  32     set: HashSet<ty::Predicate<'tcx>>
  33 }
  34
  35 /// The fulfillment context is used to drive trait resolution.  It
  36 /// consists of a list of obligations that must be (eventually)
  37 /// satisfied. The job is to track which are satisfied, which yielded
  38 /// errors, and which are still pending. At any point, users can call
  39 /// `select_where_possible`, and the fulfilment context will try to do
  40 /// selection, retaining only those obligations that remain
  41 /// ambiguous. This may be helpful in pushing type inference
  42 /// along. Once all type inference constraints have been generated, the
  43 /// method `select_all_or_error` can be used to report any remaining
  44 /// ambiguous cases as errors.
  45 pub struct FulfillmentContext<'tcx> {
  46     // a simple cache that aims to cache *exact duplicate obligations*
  47     // and avoid adding them twice. This serves a different purpose
  48     // than the `SelectionCache`: it avoids duplicate errors and
  49     // permits recursive obligations, which are often generated from
  50     // traits like `Send` et al.
  51     duplicate_set: FulfilledPredicates<'tcx>,
  52
  53     // A list of all obligations that have been registered with this
  54     // fulfillment context.
  55     predicates: Vec<PredicateObligation<'tcx>>,
  56
  57     // Remembers the count of trait obligations that we have already
  58     // attempted to select. This is used to avoid repeating work
  59     // when `select_new_obligations` is called.
  60     attempted_mark: usize,
  61
  62     // A set of constraints that regionck must validate. Each
  63     // constraint has the form `T:'a`, meaning "some type `T` must
  64     // outlive the lifetime 'a". These constraints derive from
  65     // instantiated type parameters. So if you had a struct defined
  66     // like
  67     //
  68     //     struct Foo<T:'static> { ... }
  69     //
  70     // then in some expression `let x = Foo { ... }` it will
  71     // instantiate the type parameter `T` with a fresh type `$0`. At
  72     // the same time, it will record a region obligation of
  73     // `$0:'static`. This will get checked later by regionck. (We
  74     // can't generally check these things right away because we have
  75     // to wait until types are resolved.)
  76     //
  77     // These are stored in a map keyed to the id of the innermost
  78     // enclosing fn body / static initializer expression. This is
  79     // because the location where the obligation was incurred can be
  80     // relevant with respect to which sublifetime assumptions are in
  81     // place. The reason that we store under the fn-id, and not
  82     // something more fine-grained, is so that it is easier for
  83     // regionck to be sure that it has found *all* the region
  84     // obligations (otherwise, it's easy to fail to walk to a
  85     // particular node-id).
  86     region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>,
  87
  88     errors_will_be_reported: bool,
  89 }
  90
  91 #[derive(Clone)]
  92 pub struct RegionObligation<'tcx> {
  93     pub sub_region: ty::Region,
  94     pub sup_type: Ty<'tcx>,
  95     pub cause: ObligationCause<'tcx>,
  96 }
  97
  98 impl<'tcx> FulfillmentContext<'tcx> {
  99     /// Creates a new fulfillment context.
 100     ///
 101     /// `errors_will_be_reported` indicates whether ALL errors that
 102     /// are generated by this fulfillment context will be reported to
 103     /// the end user. This is used to inform caching, because it
 104     /// allows us to conclude that traits that resolve successfully
 105     /// will in fact always resolve successfully (in particular, it
 106     /// guarantees that if some dependent obligation encounters a
 107     /// problem, compilation will be aborted).  If you're not sure of
 108     /// the right value here, pass `false`, as that is the more
 109     /// conservative option.
 110     ///
 111     /// FIXME -- a better option would be to hold back on modifying
 112     /// the global cache until we know that all dependent obligations
 113     /// are also satisfied. In that case, we could actually remove
 114     /// this boolean flag, and we'd also avoid the problem of squelching
 115     /// duplicate errors that occur across fns.
 116     pub fn new(errors_will_be_reported: bool) -> FulfillmentContext<'tcx> {
 117         FulfillmentContext {
 118             duplicate_set: FulfilledPredicates::new(),
 119             predicates: Vec::new(),
 120             attempted_mark: 0,
 121             region_obligations: NodeMap(),
 122             errors_will_be_reported: errors_will_be_reported,
 123         }
 124     }
 125
 126     /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by
 127     /// creating a fresh type variable `$0` as well as a projection
 128     /// predicate `<SomeType as SomeTrait>::X == $0`. When the
 129     /// inference engine runs, it will attempt to find an impl of
 130     /// `SomeTrait` or a where clause that lets us unify `$0` with
 131     /// something concrete. If this fails, we'll unify `$0` with
 132     /// `projection_ty` again.
 133     pub fn normalize_projection_type<'a>(&mut self,
 134                                          infcx: &InferCtxt<'a,'tcx>,
 135                                          typer: &ty::ClosureTyper<'tcx>,
 136                                          projection_ty: ty::ProjectionTy<'tcx>,
 137                                          cause: ObligationCause<'tcx>)
 138                                          -> Ty<'tcx>
 139     {
 140         debug!("normalize_associated_type(projection_ty={:?})",
 141                projection_ty);
 142
 143         assert!(!projection_ty.has_escaping_regions());
 144
 145         // FIXME(#20304) -- cache
 146
 147         let mut selcx = SelectionContext::new(infcx, typer);
 148         let normalized = project::normalize_projection_type(&mut selcx, projection_ty, cause, 0);
 149
 150         for obligation in normalized.obligations {
 151             self.register_predicate_obligation(infcx, obligation);
 152         }
 153
 154         debug!("normalize_associated_type: result={:?}", normalized.value);
 155
 156         normalized.value
 157     }
 158
 159     pub fn register_builtin_bound<'a>(&mut self,
 160                                       infcx: &InferCtxt<'a,'tcx>,
 161                                       ty: Ty<'tcx>,
 162                                       builtin_bound: ty::BuiltinBound,
 163                                       cause: ObligationCause<'tcx>)
 164     {
 165         match predicate_for_builtin_bound(infcx.tcx, cause, builtin_bound, 0, ty) {
 166             Ok(predicate) => {
 167                 self.register_predicate_obligation(infcx, predicate);
 168             }
 169             Err(ErrorReported) => { }
 170         }
 171     }
 172
 173     pub fn register_region_obligation<'a>(&mut self,
 174                                           t_a: Ty<'tcx>,
 175                                           r_b: ty::Region,
 176                                           cause: ObligationCause<'tcx>)
 177     {
 178         register_region_obligation(t_a, r_b, cause, &mut self.region_obligations);
 179     }
 180
 181     pub fn register_predicate_obligation<'a>(&mut self,
 182                                              infcx: &InferCtxt<'a,'tcx>,
 183                                              obligation: PredicateObligation<'tcx>)
 184     {
 185         // this helps to reduce duplicate errors, as well as making
 186         // debug output much nicer to read and so on.
 187         let obligation = infcx.resolve_type_vars_if_possible(&obligation);
 188
 189         assert!(!obligation.has_escaping_regions());
 190
 191         if self.is_duplicate_or_add(infcx.tcx, &obligation.predicate) {
 192             debug!("register_predicate({:?}) -- already seen, skip", obligation);
 193             return;
 194         }
 195
 196         debug!("register_predicate({:?})", obligation);
 197         self.predicates.push(obligation);
 198     }
 199
 200     pub fn region_obligations(&self,
 201                               body_id: ast::NodeId)
 202                               -> &[RegionObligation<'tcx>]
 203     {
 204         match self.region_obligations.get(&body_id) {
 205             None => Default::default(),
 206             Some(vec) => vec,
 207         }
 208     }
 209
 210     pub fn select_all_or_error<'a>(&mut self,
 211                                    infcx: &InferCtxt<'a,'tcx>,
 212                                    typer: &ty::ClosureTyper<'tcx>)
 213                                    -> Result<(),Vec<FulfillmentError<'tcx>>>
 214     {
 215         try!(self.select_where_possible(infcx, typer));
 216
 217         // Anything left is ambiguous.
 218         let errors: Vec<FulfillmentError> =
 219             self.predicates
 220             .iter()
 221             .map(|o| FulfillmentError::new((*o).clone(), CodeAmbiguity))
 222             .collect();
 223
 224         if errors.is_empty() {
 225             Ok(())
 226         } else {
 227             Err(errors)
 228         }
 229     }
 230
 231     /// Attempts to select obligations that were registered since the call to a selection routine.
 232     /// This is used by the type checker to eagerly attempt to resolve obligations in hopes of
 233     /// gaining type information. It'd be equally valid to use `select_where_possible` but it
 234     /// results in `O(n^2)` performance (#18208).
 235     pub fn select_new_obligations<'a>(&mut self,
 236                                       infcx: &InferCtxt<'a,'tcx>,
 237                                       typer: &ty::ClosureTyper<'tcx>)
 238                                       -> Result<(),Vec<FulfillmentError<'tcx>>>
 239     {
 240         let mut selcx = SelectionContext::new(infcx, typer);
 241         self.select(&mut selcx, true)
 242     }
 243
 244     pub fn select_where_possible<'a>(&mut self,
 245                                      infcx: &InferCtxt<'a,'tcx>,
 246                                      typer: &ty::ClosureTyper<'tcx>)
 247                                      -> Result<(),Vec<FulfillmentError<'tcx>>>
 248     {
 249         let mut selcx = SelectionContext::new(infcx, typer);
 250         self.select(&mut selcx, false)
 251     }
 252
 253     pub fn pending_obligations(&self) -> &[PredicateObligation<'tcx>] {
 254         &self.predicates
 255     }
 256
 257     fn is_duplicate_or_add(&mut self, tcx: &ty::ctxt<'tcx>,
 258                            predicate: &ty::Predicate<'tcx>)
 259                            -> bool {
 260         // This is a kind of dirty hack to allow us to avoid "rederiving"
 261         // things that we have already proven in other methods.
 262         //
 263         // The idea is that any predicate that doesn't involve type
 264         // parameters and which only involves the 'static region (and
 265         // no other regions) is universally solvable, since impls are global.
 266         //
 267         // This is particularly important since even if we have a
 268         // cache hit in the selection context, we still wind up
 269         // evaluating the 'nested obligations'.  This cache lets us
 270         // skip those.
 271
 272         if self.errors_will_be_reported && predicate.is_global() {
 273             tcx.fulfilled_predicates.borrow_mut().is_duplicate_or_add(predicate)
 274         } else {
 275             self.duplicate_set.is_duplicate_or_add(predicate)
 276         }
 277     }
 278
 279     /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
 280     /// only attempts to select obligations that haven't been seen before.
 281     fn select<'a>(&mut self,
 282                   selcx: &mut SelectionContext<'a, 'tcx>,
 283                   only_new_obligations: bool)
 284                   -> Result<(),Vec<FulfillmentError<'tcx>>>
 285     {
 286         debug!("select({} obligations, only_new_obligations={}) start",
 287                self.predicates.len(),
 288                only_new_obligations);
 289
 290         let mut errors = Vec::new();
 291
 292         loop {
 293             let count = self.predicates.len();
 294
 295             debug!("select_where_possible({} obligations) iteration",
 296                    count);
 297
 298             let mut new_obligations = Vec::new();
 299
 300             // If we are only attempting obligations we haven't seen yet,
 301             // then set `skip` to the number of obligations we've already
 302             // seen.
 303             let mut skip = if only_new_obligations {
 304                 self.attempted_mark
 305             } else {
 306                 0
 307             };
 308
 309             // First pass: walk each obligation, retaining
 310             // only those that we cannot yet process.
 311             {
 312                 let region_obligations = &mut self.region_obligations;
 313                 self.predicates.retain(|predicate| {
 314                     // Hack: Retain does not pass in the index, but we want
 315                     // to avoid processing the first `start_count` entries.
 316                     let processed =
 317                         if skip == 0 {
 318                             process_predicate(selcx, predicate,
 319                                               &mut new_obligations, &mut errors, region_obligations)
 320                         } else {
 321                             skip -= 1;
 322                             false
 323                         };
 324                     !processed
 325                 });
 326             }
 327
 328             self.attempted_mark = self.predicates.len();
 329
 330             if self.predicates.len() == count {
 331                 // Nothing changed.
 332                 break;
 333             }
 334
 335             // Now go through all the successful ones,
 336             // registering any nested obligations for the future.
 337             for new_obligation in new_obligations {
 338                 self.register_predicate_obligation(selcx.infcx(), new_obligation);
 339             }
 340         }
 341
 342         debug!("select({} obligations, {} errors) done",
 343                self.predicates.len(),
 344                errors.len());
 345
 346         if errors.is_empty() {
 347             Ok(())
 348         } else {
 349             Err(errors)
 350         }
 351     }
 352 }
 353
 354 fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
 355                               obligation: &PredicateObligation<'tcx>,
 356                               new_obligations: &mut Vec<PredicateObligation<'tcx>>,
 357                               errors: &mut Vec<FulfillmentError<'tcx>>,
 358                               region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
 359                               -> bool
 360 {
 361     /*!
 362      * Processes a predicate obligation and modifies the appropriate
 363      * output array with the successful/error result.  Returns `false`
 364      * if the predicate could not be processed due to insufficient
 365      * type inference.
 366      */
 367
 368     match obligation.predicate {
 369         ty::Predicate::Trait(ref data) => {
 370             let trait_obligation = obligation.with(data.clone());
 371             match selcx.select(&trait_obligation) {
 372                 Ok(None) => {
 373                     false
 374                 }
 375                 Ok(Some(s)) => {
 376                     new_obligations.append(&mut s.nested_obligations());
 377                     true
 378                 }
 379                 Err(selection_err) => {
 380                     debug!("predicate: {:?} error: {:?}",
 381                            obligation,
 382                            selection_err);
 383                     errors.push(
 384                         FulfillmentError::new(
 385                             obligation.clone(),
 386                             CodeSelectionError(selection_err)));
 387                     true
 388                 }
 389             }
 390         }
 391
 392         ty::Predicate::Equate(ref binder) => {
 393             match selcx.infcx().equality_predicate(obligation.cause.span, binder) {
 394                 Ok(()) => { }
 395                 Err(_) => {
 396                     errors.push(
 397                         FulfillmentError::new(
 398                             obligation.clone(),
 399                             CodeSelectionError(Unimplemented)));
 400                 }
 401             }
 402             true
 403         }
 404
 405         ty::Predicate::RegionOutlives(ref binder) => {
 406             match selcx.infcx().region_outlives_predicate(obligation.cause.span, binder) {
 407                 Ok(()) => { }
 408                 Err(_) => {
 409                     errors.push(
 410                         FulfillmentError::new(
 411                             obligation.clone(),
 412                             CodeSelectionError(Unimplemented)));
 413                 }
 414             }
 415
 416             true
 417         }
 418
 419         ty::Predicate::TypeOutlives(ref binder) => {
 420             // For now, we just check that there are no higher-ranked
 421             // regions.  If there are, we will call this obligation an
 422             // error. Eventually we should be able to support some
 423             // cases here, I imagine (e.g., `for<'a> int : 'a`).
 424             if ty::count_late_bound_regions(selcx.tcx(), binder) != 0 {
 425                 errors.push(
 426                     FulfillmentError::new(
 427                         obligation.clone(),
 428                         CodeSelectionError(Unimplemented)));
 429             } else {
 430                 let ty::OutlivesPredicate(t_a, r_b) = binder.0;
 431                 register_region_obligation(t_a, r_b,
 432                                            obligation.cause.clone(),
 433                                            region_obligations);
 434             }
 435             true
 436         }
 437
 438         ty::Predicate::Projection(ref data) => {
 439             let project_obligation = obligation.with(data.clone());
 440             let result = project::poly_project_and_unify_type(selcx, &project_obligation);
 441             debug!("process_predicate: poly_project_and_unify_type({:?}) returned {:?}",
 442                    project_obligation,
 443                    result);
 444             match result {
 445                 Ok(Some(obligations)) => {
 446                     new_obligations.extend(obligations);
 447                     true
 448                 }
 449                 Ok(None) => {
 450                     false
 451                 }
 452                 Err(err) => {
 453                     errors.push(
 454                         FulfillmentError::new(
 455                             obligation.clone(),
 456                             CodeProjectionError(err)));
 457                     true
 458                 }
 459             }
 460         }
 461     }
 462 }
 463
 464 impl<'tcx> fmt::Debug for RegionObligation<'tcx> {
 465     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 466         write!(f, "RegionObligation(sub_region={:?}, sup_type={:?})",
 467                self.sub_region,
 468                self.sup_type)
 469     }
 470 }
 471
 472 fn register_region_obligation<'tcx>(t_a: Ty<'tcx>,
 473                                     r_b: ty::Region,
 474                                     cause: ObligationCause<'tcx>,
 475                                     region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
 476 {
 477     let region_obligation = RegionObligation { sup_type: t_a,
 478                                                sub_region: r_b,
 479                                                cause: cause };
 480
 481     debug!("register_region_obligation({:?})",
 482            region_obligation);
 483
 484     region_obligations.entry(region_obligation.cause.body_id).or_insert(vec![])
 485         .push(region_obligation);
 486
 487 }
 488
 489 impl<'tcx> FulfilledPredicates<'tcx> {
 490     pub fn new() -> FulfilledPredicates<'tcx> {
 491         FulfilledPredicates {
 492             set: HashSet::new()
 493         }
 494     }
 495
 496     pub fn is_duplicate(&self, p: &ty::Predicate<'tcx>) -> bool {
 497         self.set.contains(p)
 498     }
 499
 500     fn is_duplicate_or_add(&mut self, p: &ty::Predicate<'tcx>) -> bool {
 501         !self.set.insert(p.clone())
 502     }
 503 }
 504
 505