src/librustc/traits/codegen/mod.rs

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