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