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