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