src/librustc/traits/query/outlives_bounds.rs

   1 // Copyright 2012-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::InferCtxt;
  12 use syntax::ast;
  13 use syntax::source_map::Span;
  14 use rustc_data_structures::small_vec::SmallVec;
  15 use traits::{FulfillmentContext, ObligationCause, TraitEngine, TraitEngineExt};
  16 use traits::query::NoSolution;
  17 use ty::{self, Ty, TyCtxt};
  18
  19 use ich::StableHashingContext;
  20 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
  21                                            StableHasherResult};
  22 use std::mem;
  23
  24 /// Outlives bounds are relationships between generic parameters,
  25 /// whether they both be regions (`'a: 'b`) or whether types are
  26 /// involved (`T: 'a`).  These relationships can be extracted from the
  27 /// full set of predicates we understand or also from types (in which
  28 /// case they are called implied bounds). They are fed to the
  29 /// `OutlivesEnv` which in turn is supplied to the region checker and
  30 /// other parts of the inference system.
  31 #[derive(Clone, Debug)]
  32 pub enum OutlivesBound<'tcx> {
  33     RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
  34     RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
  35     RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>),
  36 }
  37
  38 EnumLiftImpl! {
  39     impl<'a, 'tcx> Lift<'tcx> for self::OutlivesBound<'a> {
  40         type Lifted = self::OutlivesBound<'tcx>;
  41         (self::OutlivesBound::RegionSubRegion)(a, b),
  42         (self::OutlivesBound::RegionSubParam)(a, b),
  43         (self::OutlivesBound::RegionSubProjection)(a, b),
  44     }
  45 }
  46
  47 EnumTypeFoldableImpl! {
  48     impl<'tcx> TypeFoldable<'tcx> for self::OutlivesBound<'tcx> {
  49         (self::OutlivesBound::RegionSubRegion)(a, b),
  50         (self::OutlivesBound::RegionSubParam)(a, b),
  51         (self::OutlivesBound::RegionSubProjection)(a, b),
  52     }
  53 }
  54
  55 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for OutlivesBound<'tcx> {
  56     fn hash_stable<W: StableHasherResult>(&self,
  57                                           hcx: &mut StableHashingContext<'a>,
  58                                           hasher: &mut StableHasher<W>) {
  59         mem::discriminant(self).hash_stable(hcx, hasher);
  60         match *self {
  61             OutlivesBound::RegionSubRegion(ref a, ref b) => {
  62                 a.hash_stable(hcx, hasher);
  63                 b.hash_stable(hcx, hasher);
  64             }
  65             OutlivesBound::RegionSubParam(ref a, ref b) => {
  66                 a.hash_stable(hcx, hasher);
  67                 b.hash_stable(hcx, hasher);
  68             }
  69             OutlivesBound::RegionSubProjection(ref a, ref b) => {
  70                 a.hash_stable(hcx, hasher);
  71                 b.hash_stable(hcx, hasher);
  72             }
  73         }
  74     }
  75 }
  76
  77 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
  78     /// Implied bounds are region relationships that we deduce
  79     /// automatically.  The idea is that (e.g.) a caller must check that a
  80     /// function's argument types are well-formed immediately before
  81     /// calling that fn, and hence the *callee* can assume that its
  82     /// argument types are well-formed. This may imply certain relationships
  83     /// between generic parameters. For example:
  84     ///
  85     ///     fn foo<'a,T>(x: &'a T)
  86     ///
  87     /// can only be called with a `'a` and `T` such that `&'a T` is WF.
  88     /// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`.
  89     ///
  90     /// # Parameters
  91     ///
  92     /// - `param_env`, the where-clauses in scope
  93     /// - `body_id`, the body-id to use when normalizing assoc types.
  94     ///   Note that this may cause outlives obligations to be injected
  95     ///   into the inference context with this body-id.
  96     /// - `ty`, the type that we are supposed to assume is WF.
  97     /// - `span`, a span to use when normalizing, hopefully not important,
  98     ///   might be useful if a `bug!` occurs.
  99     pub fn implied_outlives_bounds(
 100         &self,
 101         param_env: ty::ParamEnv<'tcx>,
 102         body_id: ast::NodeId,
 103         ty: Ty<'tcx>,
 104         span: Span,
 105     ) -> Vec<OutlivesBound<'tcx>> {
 106         debug!("implied_outlives_bounds(ty = {:?})", ty);
 107
 108         let mut orig_values = SmallVec::new();
 109         let key = self.canonicalize_query(&param_env.and(ty), &mut orig_values);
 110         let result = match self.tcx.global_tcx().implied_outlives_bounds(key) {
 111             Ok(r) => r,
 112             Err(NoSolution) => {
 113                 self.tcx.sess.delay_span_bug(
 114                     span,
 115                     "implied_outlives_bounds failed to solve all obligations"
 116                 );
 117                 return vec![];
 118             }
 119         };
 120         assert!(result.value.is_proven());
 121
 122         let result = self.instantiate_query_result_and_region_obligations(
 123             &ObligationCause::misc(span, body_id), param_env, &orig_values, &result);
 124         debug!("implied_outlives_bounds for {:?}: {:#?}", ty, result);
 125         let result = match result {
 126             Ok(v) => v,
 127             Err(_) => {
 128                 self.tcx.sess.delay_span_bug(
 129                     span,
 130                     "implied_outlives_bounds failed to instantiate"
 131                 );
 132                 return vec![];
 133             }
 134         };
 135
 136         // Instantiation may have produced new inference variables and constraints on those
 137         // variables. Process these constraints.
 138         let mut fulfill_cx = FulfillmentContext::new();
 139         fulfill_cx.register_predicate_obligations(self, result.obligations);
 140         if fulfill_cx.select_all_or_error(self).is_err() {
 141             self.tcx.sess.delay_span_bug(
 142                 span,
 143                 "implied_outlives_bounds failed to solve obligations from instantiation"
 144             );
 145         }
 146
 147         result.value
 148     }
 149 }
 150
 151 pub fn explicit_outlives_bounds<'tcx>(
 152     param_env: ty::ParamEnv<'tcx>,
 153 ) -> impl Iterator<Item = OutlivesBound<'tcx>> + 'tcx {
 154     debug!("explicit_outlives_bounds()");
 155     param_env
 156         .caller_bounds
 157         .into_iter()
 158         .filter_map(move |predicate| match predicate {
 159             ty::Predicate::Projection(..) |
 160             ty::Predicate::Trait(..) |
 161             ty::Predicate::Subtype(..) |
 162             ty::Predicate::WellFormed(..) |
 163             ty::Predicate::ObjectSafe(..) |
 164             ty::Predicate::ClosureKind(..) |
 165             ty::Predicate::TypeOutlives(..) |
 166             ty::Predicate::ConstEvaluatable(..) => None,
 167             ty::Predicate::RegionOutlives(ref data) => data.no_late_bound_regions().map(
 168                 |ty::OutlivesPredicate(r_a, r_b)| OutlivesBound::RegionSubRegion(r_b, r_a),
 169             ),
 170         })
 171 }