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 std::marker::PhantomData;
  18 use syntax_pos::DUMMY_SP;
  19 use infer::InferCtxt;
  20 use syntax_pos::Span;
  21 use traits::{FulfillmentContext, Obligation, ObligationCause, SelectionContext,
  22              TraitEngine, Vtable};
  23 use ty::{self, Ty, TyCtxt};
  24 use ty::subst::{Subst, Substs};
  25 use ty::fold::TypeFoldable;
  26
  27 /// Attempts to resolve an obligation to a vtable.. The result is
  28 /// a shallow vtable resolution -- meaning that we do not
  29 /// (necessarily) resolve all nested obligations on the impl. Note
  30 /// that type check should guarantee to us that all nested
  31 /// obligations *could be* resolved if we wanted to.
  32 /// Assumes that this is run after the entire crate has been successfully type-checked.
  33 pub fn trans_fulfill_obligation<'a, 'tcx>(ty: TyCtxt<'a, 'tcx, 'tcx>,
  34                                           (param_env, trait_ref):
  35                                           (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>))
  36                                           -> Vtable<'tcx, ()>
  37 {
  38     // Remove any references to regions; this helps improve caching.
  39     let trait_ref = ty.erase_regions(&trait_ref);
  40
  41     debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
  42             (param_env, trait_ref), trait_ref.def_id());
  43
  44     // Do the initial selection for the obligation. This yields the
  45     // shallow result we are looking for -- that is, what specific impl.
  46     ty.infer_ctxt().enter(|infcx| {
  47         let mut selcx = SelectionContext::new(&infcx);
  48
  49         let obligation_cause = ObligationCause::dummy();
  50         let obligation = Obligation::new(obligation_cause,
  51                                             param_env,
  52                                             trait_ref.to_poly_trait_predicate());
  53
  54         let selection = match selcx.select(&obligation) {
  55             Ok(Some(selection)) => selection,
  56             Ok(None) => {
  57                 // Ambiguity can happen when monomorphizing during trans
  58                 // expands to some humongo type that never occurred
  59                 // statically -- this humongo type can then overflow,
  60                 // leading to an ambiguous result. So report this as an
  61                 // overflow bug, since I believe this is the only case
  62                 // where ambiguity can result.
  63                 bug!("Encountered ambiguity selecting `{:?}` during trans, \
  64                         presuming due to overflow",
  65                         trait_ref)
  66             }
  67             Err(e) => {
  68                 bug!("Encountered error `{:?}` selecting `{:?}` during trans",
  69                             e, trait_ref)
  70             }
  71         };
  72
  73         debug!("fulfill_obligation: selection={:?}", selection);
  74
  75         // Currently, we use a fulfillment context to completely resolve
  76         // all nested obligations. This is because they can inform the
  77         // inference of the impl's type parameters.
  78         let mut fulfill_cx = FulfillmentContext::new();
  79         let vtable = selection.map(|predicate| {
  80             debug!("fulfill_obligation: register_predicate_obligation {:?}", predicate);
  81             fulfill_cx.register_predicate_obligation(&infcx, predicate);
  82         });
  83         let vtable = infcx.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &vtable);
  84
  85         info!("Cache miss: {:?} => {:?}", trait_ref, vtable);
  86         vtable
  87     })
  88 }
  89
  90 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
  91     /// Monomorphizes a type from the AST by first applying the
  92     /// in-scope substitutions and then normalizing any associated
  93     /// types.
  94     pub fn subst_and_normalize_erasing_regions<T>(
  95         self,
  96         param_substs: &Substs<'tcx>,
  97         param_env: ty::ParamEnv<'tcx>,
  98         value: &T
  99     ) -> T
 100     where
 101         T: TypeFoldable<'tcx>,
 102     {
 103         debug!(
 104             "subst_and_normalize_erasing_regions(\
 105              param_substs={:?}, \
 106              value={:?}, \
 107              param_env={:?})",
 108             param_substs,
 109             value,
 110             param_env,
 111         );
 112         let substituted = value.subst(self, param_substs);
 113         self.normalize_erasing_regions(param_env, substituted)
 114     }
 115 }
 116
 117 // Implement DepTrackingMapConfig for `trait_cache`
 118 pub struct TraitSelectionCache<'tcx> {
 119     data: PhantomData<&'tcx ()>
 120 }
 121
 122 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
 123     type Key = (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>);
 124     type Value = Vtable<'tcx, ()>;
 125     fn to_dep_kind() -> DepKind {
 126         DepKind::TraitSelect
 127     }
 128 }
 129
 130 // # Global Cache
 131
 132 pub struct ProjectionCache<'gcx> {
 133     data: PhantomData<&'gcx ()>
 134 }
 135
 136 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
 137     type Key = Ty<'gcx>;
 138     type Value = Ty<'gcx>;
 139     fn to_dep_kind() -> DepKind {
 140         DepKind::TraitSelect
 141     }
 142 }
 143
 144 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 145     /// Finishes processes any obligations that remain in the
 146     /// fulfillment context, and then returns the result with all type
 147     /// variables removed and regions erased. Because this is intended
 148     /// for use after type-check has completed, if any errors occur,
 149     /// it will panic. It is used during normalization and other cases
 150     /// where processing the obligations in `fulfill_cx` may cause
 151     /// type inference variables that appear in `result` to be
 152     /// unified, and hence we need to process those obligations to get
 153     /// the complete picture of the type.
 154     fn drain_fulfillment_cx_or_panic<T>(&self,
 155                                         span: Span,
 156                                         fulfill_cx: &mut FulfillmentContext<'tcx>,
 157                                         result: &T)
 158                                         -> T::Lifted
 159         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
 160     {
 161         debug!("drain_fulfillment_cx_or_panic()");
 162
 163         // In principle, we only need to do this so long as `result`
 164         // contains unbound type parameters. It could be a slight
 165         // optimization to stop iterating early.
 166         match fulfill_cx.select_all_or_error(self) {
 167             Ok(()) => { }
 168             Err(errors) => {
 169                 span_bug!(span, "Encountered errors `{:?}` resolving bounds after type-checking",
 170                           errors);
 171             }
 172         }
 173
 174         let result = self.resolve_type_vars_if_possible(result);
 175         let result = self.tcx.erase_regions(&result);
 176
 177         match self.tcx.lift_to_global(&result) {
 178             Some(result) => result,
 179             None => {
 180                 span_bug!(span, "Uninferred types/regions in `{:?}`", result);
 181             }
 182         }
 183     }
 184 }