src/librustc_trans/monomorphize.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 use abi::Abi;
  12 use common::*;
  13 use glue;
  14
  15 use rustc::hir::def_id::DefId;
  16 use rustc::infer::TransNormalize;
  17 use rustc::middle::lang_items::DropInPlaceFnLangItem;
  18 use rustc::traits::{self, SelectionContext, Reveal};
  19 use rustc::ty::adjustment::CustomCoerceUnsized;
  20 use rustc::ty::fold::{TypeFolder, TypeFoldable};
  21 use rustc::ty::subst::{Kind, Subst, Substs};
  22 use rustc::ty::{self, Ty, TyCtxt};
  23 use rustc::util::common::MemoizationMap;
  24
  25 use syntax::ast;
  26 use syntax::codemap::{Span, DUMMY_SP};
  27
  28 pub use rustc::ty::Instance;
  29
  30 fn fn_once_adapter_instance<'a, 'tcx>(
  31     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  32     closure_did: DefId,
  33     substs: ty::ClosureSubsts<'tcx>,
  34     ) -> Instance<'tcx> {
  35     debug!("fn_once_adapter_shim({:?}, {:?})",
  36            closure_did,
  37            substs);
  38     let fn_once = tcx.lang_items.fn_once_trait().unwrap();
  39     let call_once = tcx.associated_items(fn_once)
  40         .find(|it| it.kind == ty::AssociatedKind::Method)
  41         .unwrap().def_id;
  42     let def = ty::InstanceDef::ClosureOnceShim { call_once };
  43
  44     let self_ty = tcx.mk_closure_from_closure_substs(
  45         closure_did, substs);
  46
  47     let sig = tcx.closure_type(closure_did).subst(tcx, substs.substs);
  48     let sig = tcx.erase_late_bound_regions_and_normalize(&sig);
  49     assert_eq!(sig.inputs().len(), 1);
  50     let substs = tcx.mk_substs([
  51         Kind::from(self_ty),
  52         Kind::from(sig.inputs()[0]),
  53     ].iter().cloned());
  54
  55     debug!("fn_once_adapter_shim: self_ty={:?} sig={:?}", self_ty, sig);
  56     Instance { def, substs }
  57 }
  58
  59 fn needs_fn_once_adapter_shim(actual_closure_kind: ty::ClosureKind,
  60                               trait_closure_kind: ty::ClosureKind)
  61                               -> Result<bool, ()>
  62 {
  63     match (actual_closure_kind, trait_closure_kind) {
  64         (ty::ClosureKind::Fn, ty::ClosureKind::Fn) |
  65         (ty::ClosureKind::FnMut, ty::ClosureKind::FnMut) |
  66         (ty::ClosureKind::FnOnce, ty::ClosureKind::FnOnce) => {
  67             // No adapter needed.
  68            Ok(false)
  69         }
  70         (ty::ClosureKind::Fn, ty::ClosureKind::FnMut) => {
  71             // The closure fn `llfn` is a `fn(&self, ...)`.  We want a
  72             // `fn(&mut self, ...)`. In fact, at trans time, these are
  73             // basically the same thing, so we can just return llfn.
  74             Ok(false)
  75         }
  76         (ty::ClosureKind::Fn, ty::ClosureKind::FnOnce) |
  77         (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => {
  78             // The closure fn `llfn` is a `fn(&self, ...)` or `fn(&mut
  79             // self, ...)`.  We want a `fn(self, ...)`. We can produce
  80             // this by doing something like:
  81             //
  82             //     fn call_once(self, ...) { call_mut(&self, ...) }
  83             //     fn call_once(mut self, ...) { call_mut(&mut self, ...) }
  84             //
  85             // These are both the same at trans time.
  86             Ok(true)
  87         }
  88         _ => Err(()),
  89     }
  90 }
  91
  92 pub fn resolve_closure<'a, 'tcx> (
  93     scx: &SharedCrateContext<'a, 'tcx>,
  94     def_id: DefId,
  95     substs: ty::ClosureSubsts<'tcx>,
  96     requested_kind: ty::ClosureKind)
  97     -> Instance<'tcx>
  98 {
  99     let actual_kind = scx.tcx().closure_kind(def_id);
 100
 101     match needs_fn_once_adapter_shim(actual_kind, requested_kind) {
 102         Ok(true) => fn_once_adapter_instance(scx.tcx(), def_id, substs),
 103         _ => Instance::new(def_id, substs.substs)
 104     }
 105 }
 106
 107 /// Attempts to resolve an obligation. The result is a shallow vtable resolution -- meaning that we
 108 /// do not (necessarily) resolve all nested obligations on the impl. Note that type check should
 109 /// guarantee to us that all nested obligations *could be* resolved if we wanted to.
 110 fn fulfill_obligation<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
 111                                 span: Span,
 112                                 trait_ref: ty::PolyTraitRef<'tcx>)
 113                                 -> traits::Vtable<'tcx, ()>
 114 {
 115     let tcx = scx.tcx();
 116
 117     // Remove any references to regions; this helps improve caching.
 118     let trait_ref = tcx.erase_regions(&trait_ref);
 119
 120     scx.trait_cache().memoize(trait_ref, || {
 121         debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
 122                trait_ref, trait_ref.def_id());
 123
 124         // Do the initial selection for the obligation. This yields the
 125         // shallow result we are looking for -- that is, what specific impl.
 126         tcx.infer_ctxt((), Reveal::All).enter(|infcx| {
 127             let mut selcx = SelectionContext::new(&infcx);
 128
 129             let obligation_cause = traits::ObligationCause::misc(span,
 130                                                              ast::DUMMY_NODE_ID);
 131             let obligation = traits::Obligation::new(obligation_cause,
 132                                                      trait_ref.to_poly_trait_predicate());
 133
 134             let selection = match selcx.select(&obligation) {
 135                 Ok(Some(selection)) => selection,
 136                 Ok(None) => {
 137                     // Ambiguity can happen when monomorphizing during trans
 138                     // expands to some humongo type that never occurred
 139                     // statically -- this humongo type can then overflow,
 140                     // leading to an ambiguous result. So report this as an
 141                     // overflow bug, since I believe this is the only case
 142                     // where ambiguity can result.
 143                     debug!("Encountered ambiguity selecting `{:?}` during trans, \
 144                             presuming due to overflow",
 145                            trait_ref);
 146                     tcx.sess.span_fatal(span,
 147                         "reached the recursion limit during monomorphization \
 148                          (selection ambiguity)");
 149                 }
 150                 Err(e) => {
 151                     span_bug!(span, "Encountered error `{:?}` selecting `{:?}` during trans",
 152                               e, trait_ref)
 153                 }
 154             };
 155
 156             debug!("fulfill_obligation: selection={:?}", selection);
 157
 158             // Currently, we use a fulfillment context to completely resolve
 159             // all nested obligations. This is because they can inform the
 160             // inference of the impl's type parameters.
 161             let mut fulfill_cx = traits::FulfillmentContext::new();
 162             let vtable = selection.map(|predicate| {
 163                 debug!("fulfill_obligation: register_predicate_obligation {:?}", predicate);
 164                 fulfill_cx.register_predicate_obligation(&infcx, predicate);
 165             });
 166             let vtable = infcx.drain_fulfillment_cx_or_panic(span, &mut fulfill_cx, &vtable);
 167
 168             info!("Cache miss: {:?} => {:?}", trait_ref, vtable);
 169             vtable
 170         })
 171     })
 172 }
 173
 174 fn resolve_associated_item<'a, 'tcx>(
 175     scx: &SharedCrateContext<'a, 'tcx>,
 176     trait_item: &ty::AssociatedItem,
 177     trait_id: DefId,
 178     rcvr_substs: &'tcx Substs<'tcx>
 179 ) -> Instance<'tcx> {
 180     let tcx = scx.tcx();
 181     let def_id = trait_item.def_id;
 182     debug!("resolve_associated_item(trait_item={:?}, \
 183                                     trait_id={:?}, \
 184                                     rcvr_substs={:?})",
 185            def_id, trait_id, rcvr_substs);
 186
 187     let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs);
 188     let vtbl = fulfill_obligation(scx, DUMMY_SP, ty::Binder(trait_ref));
 189
 190     // Now that we know which impl is being used, we can dispatch to
 191     // the actual function:
 192     match vtbl {
 193         traits::VtableImpl(impl_data) => {
 194             let (def_id, substs) = traits::find_associated_item(
 195                 tcx, trait_item, rcvr_substs, &impl_data);
 196             let substs = tcx.erase_regions(&substs);
 197             ty::Instance::new(def_id, substs)
 198         }
 199         traits::VtableClosure(closure_data) => {
 200             let trait_closure_kind = tcx.lang_items.fn_trait_kind(trait_id).unwrap();
 201             resolve_closure(scx, closure_data.closure_def_id, closure_data.substs,
 202                             trait_closure_kind)
 203         }
 204         traits::VtableFnPointer(ref data) => {
 205             Instance {
 206                 def: ty::InstanceDef::FnPtrShim(trait_item.def_id, data.fn_ty),
 207                 substs: rcvr_substs
 208             }
 209         }
 210         traits::VtableObject(ref data) => {
 211             let index = tcx.get_vtable_index_of_object_method(data, def_id);
 212             Instance {
 213                 def: ty::InstanceDef::Virtual(def_id, index),
 214                 substs: rcvr_substs
 215             }
 216         }
 217         _ => {
 218             bug!("static call to invalid vtable: {:?}", vtbl)
 219         }
 220     }
 221 }
 222
 223 /// The point where linking happens. Resolve a (def_id, substs)
 224 /// pair to an instance.
 225 pub fn resolve<'a, 'tcx>(
 226     scx: &SharedCrateContext<'a, 'tcx>,
 227     def_id: DefId,
 228     substs: &'tcx Substs<'tcx>
 229 ) -> Instance<'tcx> {
 230     debug!("resolve(def_id={:?}, substs={:?})",
 231            def_id, substs);
 232     let result = if let Some(trait_def_id) = scx.tcx().trait_of_item(def_id) {
 233         debug!(" => associated item, attempting to find impl");
 234         let item = scx.tcx().associated_item(def_id);
 235         resolve_associated_item(scx, &item, trait_def_id, substs)
 236     } else {
 237         let item_type = def_ty(scx, def_id, substs);
 238         let def = match item_type.sty {
 239             ty::TyFnDef(_, _, f) if
 240                 f.abi() == Abi::RustIntrinsic ||
 241                 f.abi() == Abi::PlatformIntrinsic =>
 242             {
 243                 debug!(" => intrinsic");
 244                 ty::InstanceDef::Intrinsic(def_id)
 245             }
 246             _ => {
 247                 if Some(def_id) == scx.tcx().lang_items.drop_in_place_fn() {
 248                     let ty = substs.type_at(0);
 249                     if glue::needs_drop_glue(scx, ty) {
 250                         debug!(" => nontrivial drop glue");
 251                         ty::InstanceDef::DropGlue(def_id, Some(ty))
 252                     } else {
 253                         debug!(" => trivial drop glue");
 254                         ty::InstanceDef::DropGlue(def_id, None)
 255                     }
 256                 } else {
 257                     debug!(" => free item");
 258                     ty::InstanceDef::Item(def_id)
 259                 }
 260             }
 261         };
 262         Instance { def, substs }
 263     };
 264     debug!("resolve(def_id={:?}, substs={:?}) = {}",
 265            def_id, substs, result);
 266     result
 267 }
 268
 269 pub fn resolve_drop_in_place<'a, 'tcx>(
 270     scx: &SharedCrateContext<'a, 'tcx>,
 271     ty: Ty<'tcx>)
 272     -> ty::Instance<'tcx>
 273 {
 274     let def_id = scx.tcx().require_lang_item(DropInPlaceFnLangItem);
 275     let substs = scx.tcx().intern_substs(&[Kind::from(ty)]);
 276     resolve(scx, def_id, substs)
 277 }
 278
 279 pub fn custom_coerce_unsize_info<'scx, 'tcx>(scx: &SharedCrateContext<'scx, 'tcx>,
 280                                              source_ty: Ty<'tcx>,
 281                                              target_ty: Ty<'tcx>)
 282                                              -> CustomCoerceUnsized {
 283     let trait_ref = ty::Binder(ty::TraitRef {
 284         def_id: scx.tcx().lang_items.coerce_unsized_trait().unwrap(),
 285         substs: scx.tcx().mk_substs_trait(source_ty, &[target_ty])
 286     });
 287
 288     match fulfill_obligation(scx, DUMMY_SP, trait_ref) {
 289         traits::VtableImpl(traits::VtableImplData { impl_def_id, .. }) => {
 290             scx.tcx().coerce_unsized_info(impl_def_id).custom_kind.unwrap()
 291         }
 292         vtable => {
 293             bug!("invalid CoerceUnsized vtable: {:?}", vtable);
 294         }
 295     }
 296 }
 297
 298 /// Monomorphizes a type from the AST by first applying the in-scope
 299 /// substitutions and then normalizing any associated types.
 300 pub fn apply_param_substs<'a, 'tcx, T>(scx: &SharedCrateContext<'a, 'tcx>,
 301                                        param_substs: &Substs<'tcx>,
 302                                        value: &T)
 303                                        -> T
 304     where T: TransNormalize<'tcx>
 305 {
 306     let tcx = scx.tcx();
 307     debug!("apply_param_substs(param_substs={:?}, value={:?})", param_substs, value);
 308     let substituted = value.subst(tcx, param_substs);
 309     let substituted = scx.tcx().erase_regions(&substituted);
 310     AssociatedTypeNormalizer::new(scx).fold(&substituted)
 311 }
 312
 313 /// Returns the normalized type of a struct field
 314 pub fn field_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 315                           param_substs: &Substs<'tcx>,
 316                           f: &'tcx ty::FieldDef)
 317                           -> Ty<'tcx>
 318 {
 319     tcx.normalize_associated_type(&f.ty(tcx, param_substs))
 320 }
 321
 322 struct AssociatedTypeNormalizer<'a, 'b: 'a, 'gcx: 'b> {
 323     shared: &'a SharedCrateContext<'b, 'gcx>,
 324 }
 325
 326 impl<'a, 'b, 'gcx> AssociatedTypeNormalizer<'a, 'b, 'gcx> {
 327     fn new(shared: &'a SharedCrateContext<'b, 'gcx>) -> Self {
 328         AssociatedTypeNormalizer {
 329             shared: shared,
 330         }
 331     }
 332
 333     fn fold<T:TypeFoldable<'gcx>>(&mut self, value: &T) -> T {
 334         if !value.has_projection_types() {
 335             value.clone()
 336         } else {
 337             value.fold_with(self)
 338         }
 339     }
 340 }
 341
 342 impl<'a, 'b, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizer<'a, 'b, 'gcx> {
 343     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'gcx> {
 344         self.shared.tcx()
 345     }
 346
 347     fn fold_ty(&mut self, ty: Ty<'gcx>) -> Ty<'gcx> {
 348         if !ty.has_projection_types() {
 349             ty
 350         } else {
 351             self.shared.project_cache().memoize(ty, || {
 352                 debug!("AssociatedTypeNormalizer: ty={:?}", ty);
 353                 self.shared.tcx().normalize_associated_type(&ty)
 354             })
 355         }
 356     }
 357 }