src/librustc/traits/trans/mod.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 // This file contains various trait resolution methods used by trans.
  12 // They all assume regions can be erased and monomorphic types.  It
  13 // seems likely that they should eventually be merged into more
  14 // general routines.
  15
  16 use dep_graph::{DepKind, DepTrackingMapConfig};
  17 use infer::TransNormalize;
  18 use std::marker::PhantomData;
  19 use syntax_pos::DUMMY_SP;
  20 use traits::{FulfillmentContext, Obligation, ObligationCause, SelectionContext, Vtable};
  21 use ty::{self, Ty, TyCtxt};
  22 use ty::subst::{Subst, Substs};
  23 use ty::fold::{TypeFoldable, TypeFolder};
  24
  25 /// Attempts to resolve an obligation to a vtable.. The result is
  26 /// a shallow vtable resolution -- meaning that we do not
  27 /// (necessarily) resolve all nested obligations on the impl. Note
  28 /// that type check should guarantee to us that all nested
  29 /// obligations *could be* resolved if we wanted to.
  30 /// Assumes that this is run after the entire crate has been successfully type-checked.
  31 pub fn trans_fulfill_obligation<'a, 'tcx>(ty: TyCtxt<'a, 'tcx, 'tcx>,
  32                                           (param_env, trait_ref):
  33                                           (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>))
  34                                           -> Vtable<'tcx, ()>
  35 {
  36     // Remove any references to regions; this helps improve caching.
  37     let trait_ref = ty.erase_regions(&trait_ref);
  38
  39     debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
  40             (param_env, trait_ref), trait_ref.def_id());
  41
  42     // Do the initial selection for the obligation. This yields the
  43     // shallow result we are looking for -- that is, what specific impl.
  44     ty.infer_ctxt().enter(|infcx| {
  45         let mut selcx = SelectionContext::new(&infcx);
  46
  47         let obligation_cause = ObligationCause::dummy();
  48         let obligation = Obligation::new(obligation_cause,
  49                                             param_env,
  50                                             trait_ref.to_poly_trait_predicate());
  51
  52         let selection = match selcx.select(&obligation) {
  53             Ok(Some(selection)) => selection,
  54             Ok(None) => {
  55                 // Ambiguity can happen when monomorphizing during trans
  56                 // expands to some humongo type that never occurred
  57                 // statically -- this humongo type can then overflow,
  58                 // leading to an ambiguous result. So report this as an
  59                 // overflow bug, since I believe this is the only case
  60                 // where ambiguity can result.
  61                 bug!("Encountered ambiguity selecting `{:?}` during trans, \
  62                         presuming due to overflow",
  63                         trait_ref)
  64             }
  65             Err(e) => {
  66                 bug!("Encountered error `{:?}` selecting `{:?}` during trans",
  67                             e, trait_ref)
  68             }
  69         };
  70
  71         debug!("fulfill_obligation: selection={:?}", selection);
  72
  73         // Currently, we use a fulfillment context to completely resolve
  74         // all nested obligations. This is because they can inform the
  75         // inference of the impl's type parameters.
  76         let mut fulfill_cx = FulfillmentContext::new();
  77         let vtable = selection.map(|predicate| {
  78             debug!("fulfill_obligation: register_predicate_obligation {:?}", predicate);
  79             fulfill_cx.register_predicate_obligation(&infcx, predicate);
  80         });
  81         let vtable = infcx.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &vtable);
  82
  83         info!("Cache miss: {:?} => {:?}", trait_ref, vtable);
  84         vtable
  85     })
  86 }
  87
  88 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
  89     /// Monomorphizes a type from the AST by first applying the in-scope
  90     /// substitutions and then normalizing any associated types.
  91     pub fn trans_apply_param_substs<T>(self,
  92                                        param_substs: &Substs<'tcx>,
  93                                        value: &T)
  94                                        -> T
  95         where T: TransNormalize<'tcx>
  96     {
  97         debug!("apply_param_substs(param_substs={:?}, value={:?})", param_substs, value);
  98         let substituted = value.subst(self, param_substs);
  99         let substituted = self.erase_regions(&substituted);
 100         AssociatedTypeNormalizer::new(self).fold(&substituted)
 101     }
 102
 103     pub fn trans_apply_param_substs_env<T>(
 104         self,
 105         param_substs: &Substs<'tcx>,
 106         param_env: ty::ParamEnv<'tcx>,
 107         value: &T,
 108     ) -> T
 109     where
 110         T: TransNormalize<'tcx>,
 111     {
 112         debug!(
 113             "apply_param_substs_env(param_substs={:?}, value={:?}, param_env={:?})",
 114             param_substs,
 115             value,
 116             param_env,
 117         );
 118         let substituted = value.subst(self, param_substs);
 119         let substituted = self.erase_regions(&substituted);
 120         AssociatedTypeNormalizerEnv::new(self, param_env).fold(&substituted)
 121     }
 122 }
 123
 124 struct AssociatedTypeNormalizer<'a, 'gcx: 'a> {
 125     tcx: TyCtxt<'a, 'gcx, 'gcx>,
 126 }
 127
 128 impl<'a, 'gcx> AssociatedTypeNormalizer<'a, 'gcx> {
 129     fn new(tcx: TyCtxt<'a, 'gcx, 'gcx>) -> Self {
 130         AssociatedTypeNormalizer { tcx }
 131     }
 132
 133     fn fold<T:TypeFoldable<'gcx>>(&mut self, value: &T) -> T {
 134         if !value.has_projections() {
 135             value.clone()
 136         } else {
 137             value.fold_with(self)
 138         }
 139     }
 140 }
 141
 142 impl<'a, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizer<'a, 'gcx> {
 143     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'gcx> {
 144         self.tcx
 145     }
 146
 147     fn fold_ty(&mut self, ty: Ty<'gcx>) -> Ty<'gcx> {
 148         if !ty.has_projections() {
 149             ty
 150         } else {
 151             debug!("AssociatedTypeNormalizer: ty={:?}", ty);
 152             self.tcx.fully_normalize_monormophic_ty(ty)
 153         }
 154     }
 155 }
 156
 157 struct AssociatedTypeNormalizerEnv<'a, 'gcx: 'a> {
 158     tcx: TyCtxt<'a, 'gcx, 'gcx>,
 159     param_env: ty::ParamEnv<'gcx>,
 160 }
 161
 162 impl<'a, 'gcx> AssociatedTypeNormalizerEnv<'a, 'gcx> {
 163     fn new(tcx: TyCtxt<'a, 'gcx, 'gcx>, param_env: ty::ParamEnv<'gcx>) -> Self {
 164         Self { tcx, param_env }
 165     }
 166
 167     fn fold<T: TypeFoldable<'gcx>>(&mut self, value: &T) -> T {
 168         if !value.has_projections() {
 169             value.clone()
 170         } else {
 171             value.fold_with(self)
 172         }
 173     }
 174 }
 175
 176 impl<'a, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizerEnv<'a, 'gcx> {
 177     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'gcx> {
 178         self.tcx
 179     }
 180
 181     fn fold_ty(&mut self, ty: Ty<'gcx>) -> Ty<'gcx> {
 182         if !ty.has_projections() {
 183             ty
 184         } else {
 185             debug!("AssociatedTypeNormalizerEnv: ty={:?}", ty);
 186             self.tcx.normalize_associated_type_in_env(&ty, self.param_env)
 187         }
 188     }
 189 }
 190
 191 // Implement DepTrackingMapConfig for `trait_cache`
 192 pub struct TraitSelectionCache<'tcx> {
 193     data: PhantomData<&'tcx ()>
 194 }
 195
 196 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
 197     type Key = (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>);
 198     type Value = Vtable<'tcx, ()>;
 199     fn to_dep_kind() -> DepKind {
 200         DepKind::TraitSelect
 201     }
 202 }
 203
 204 // # Global Cache
 205
 206 pub struct ProjectionCache<'gcx> {
 207     data: PhantomData<&'gcx ()>
 208 }
 209
 210 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
 211     type Key = Ty<'gcx>;
 212     type Value = Ty<'gcx>;
 213     fn to_dep_kind() -> DepKind {
 214         DepKind::TraitSelect
 215     }
 216 }
 217