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::{DepGraph, DepKind, DepTrackingMap, DepTrackingMapConfig};
  17 use infer::TransNormalize;
  18 use std::cell::RefCell;
  19 use std::marker::PhantomData;
  20 use syntax::ast;
  21 use syntax_pos::Span;
  22 use traits::{FulfillmentContext, Obligation, ObligationCause, Reveal, SelectionContext, Vtable};
  23 use ty::{self, Ty, TyCtxt};
  24 use ty::subst::{Subst, Substs};
  25 use ty::fold::{TypeFoldable, TypeFolder};
  26 use util::common::MemoizationMap;
  27
  28 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
  29     /// Attempts to resolve an obligation to a vtable.. The result is
  30     /// a shallow vtable resolution -- meaning that we do not
  31     /// (necessarily) resolve all nested obligations on the impl. Note
  32     /// that type check should guarantee to us that all nested
  33     /// obligations *could be* resolved if we wanted to.
  34     pub fn trans_fulfill_obligation(self,
  35                                     span: Span,
  36                                     trait_ref: ty::PolyTraitRef<'tcx>)
  37                                     -> Vtable<'tcx, ()>
  38     {
  39         // Remove any references to regions; this helps improve caching.
  40         let trait_ref = self.erase_regions(&trait_ref);
  41
  42         self.trans_trait_caches.trait_cache.memoize(trait_ref, || {
  43             debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
  44                    trait_ref, trait_ref.def_id());
  45
  46             // Do the initial selection for the obligation. This yields the
  47             // shallow result we are looking for -- that is, what specific impl.
  48             self.infer_ctxt().enter(|infcx| {
  49                 let mut selcx = SelectionContext::new(&infcx);
  50
  51                 let param_env = ty::ParamEnv::empty(Reveal::All);
  52                 let obligation_cause = ObligationCause::misc(span,
  53                                                              ast::DUMMY_NODE_ID);
  54                 let obligation = Obligation::new(obligation_cause,
  55                                                  param_env,
  56                                                  trait_ref.to_poly_trait_predicate());
  57
  58                 let selection = match selcx.select(&obligation) {
  59                     Ok(Some(selection)) => selection,
  60                     Ok(None) => {
  61                         // Ambiguity can happen when monomorphizing during trans
  62                         // expands to some humongo type that never occurred
  63                         // statically -- this humongo type can then overflow,
  64                         // leading to an ambiguous result. So report this as an
  65                         // overflow bug, since I believe this is the only case
  66                         // where ambiguity can result.
  67                         debug!("Encountered ambiguity selecting `{:?}` during trans, \
  68                                 presuming due to overflow",
  69                                trait_ref);
  70                         self.sess.span_fatal(span,
  71                                             "reached the recursion limit during monomorphization \
  72                                              (selection ambiguity)");
  73                     }
  74                     Err(e) => {
  75                         span_bug!(span, "Encountered error `{:?}` selecting `{:?}` during trans",
  76                                   e, trait_ref)
  77                     }
  78                 };
  79
  80                 debug!("fulfill_obligation: selection={:?}", selection);
  81
  82                 // Currently, we use a fulfillment context to completely resolve
  83                 // all nested obligations. This is because they can inform the
  84                 // inference of the impl's type parameters.
  85                 let mut fulfill_cx = FulfillmentContext::new();
  86                 let vtable = selection.map(|predicate| {
  87                     debug!("fulfill_obligation: register_predicate_obligation {:?}", predicate);
  88                     fulfill_cx.register_predicate_obligation(&infcx, predicate);
  89                 });
  90                 let vtable = infcx.drain_fulfillment_cx_or_panic(span, &mut fulfill_cx, &vtable);
  91
  92                 info!("Cache miss: {:?} => {:?}", trait_ref, vtable);
  93                 vtable
  94             })
  95         })
  96     }
  97
  98     /// Monomorphizes a type from the AST by first applying the in-scope
  99     /// substitutions and then normalizing any associated types.
 100     pub fn trans_apply_param_substs<T>(self,
 101                                        param_substs: &Substs<'tcx>,
 102                                        value: &T)
 103                                        -> T
 104         where T: TransNormalize<'tcx>
 105     {
 106         debug!("apply_param_substs(param_substs={:?}, value={:?})", param_substs, value);
 107         let substituted = value.subst(self, param_substs);
 108         let substituted = self.erase_regions(&substituted);
 109         AssociatedTypeNormalizer::new(self).fold(&substituted)
 110     }
 111 }
 112
 113 struct AssociatedTypeNormalizer<'a, 'gcx: 'a> {
 114     tcx: TyCtxt<'a, 'gcx, 'gcx>,
 115 }
 116
 117 impl<'a, 'gcx> AssociatedTypeNormalizer<'a, 'gcx> {
 118     fn new(tcx: TyCtxt<'a, 'gcx, 'gcx>) -> Self {
 119         AssociatedTypeNormalizer { tcx }
 120     }
 121
 122     fn fold<T:TypeFoldable<'gcx>>(&mut self, value: &T) -> T {
 123         if !value.has_projections() {
 124             value.clone()
 125         } else {
 126             value.fold_with(self)
 127         }
 128     }
 129 }
 130
 131 impl<'a, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizer<'a, 'gcx> {
 132     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'gcx> {
 133         self.tcx
 134     }
 135
 136     fn fold_ty(&mut self, ty: Ty<'gcx>) -> Ty<'gcx> {
 137         if !ty.has_projections() {
 138             ty
 139         } else {
 140             self.tcx.trans_trait_caches.project_cache.memoize(ty, || {
 141                 debug!("AssociatedTypeNormalizer: ty={:?}", ty);
 142                 self.tcx.normalize_associated_type(&ty)
 143             })
 144         }
 145     }
 146 }
 147
 148 /// Specializes caches used in trans -- in particular, they assume all
 149 /// types are fully monomorphized and that free regions can be erased.
 150 pub struct TransTraitCaches<'tcx> {
 151     trait_cache: RefCell<DepTrackingMap<TraitSelectionCache<'tcx>>>,
 152     project_cache: RefCell<DepTrackingMap<ProjectionCache<'tcx>>>,
 153 }
 154
 155 impl<'tcx> TransTraitCaches<'tcx> {
 156     pub fn new(graph: DepGraph) -> Self {
 157         TransTraitCaches {
 158             trait_cache: RefCell::new(DepTrackingMap::new(graph.clone())),
 159             project_cache: RefCell::new(DepTrackingMap::new(graph)),
 160         }
 161     }
 162 }
 163
 164 // Implement DepTrackingMapConfig for `trait_cache`
 165 pub struct TraitSelectionCache<'tcx> {
 166     data: PhantomData<&'tcx ()>
 167 }
 168
 169 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
 170     type Key = ty::PolyTraitRef<'tcx>;
 171     type Value = Vtable<'tcx, ()>;
 172     fn to_dep_kind() -> DepKind {
 173         DepKind::TraitSelect
 174     }
 175 }
 176
 177 // # Global Cache
 178
 179 pub struct ProjectionCache<'gcx> {
 180     data: PhantomData<&'gcx ()>
 181 }
 182
 183 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
 184     type Key = Ty<'gcx>;
 185     type Value = Ty<'gcx>;
 186     fn to_dep_kind() -> DepKind {
 187         DepKind::TraitSelect
 188     }
 189 }
 190