src/librustc_trans/meth.rs

   1 // Copyright 2012 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 std::rc::Rc;
  12
  13 use attributes;
  14 use arena::TypedArena;
  15 use back::symbol_names;
  16 use llvm::{ValueRef, get_params};
  17 use rustc::hir::def_id::DefId;
  18 use rustc::ty::subst::{FnSpace, Subst, Substs};
  19 use rustc::ty::subst;
  20 use rustc::traits::{self, ProjectionMode};
  21 use abi::FnType;
  22 use base::*;
  23 use build::*;
  24 use callee::{Callee, Virtual, ArgVals, trans_fn_pointer_shim};
  25 use closure;
  26 use common::*;
  27 use consts;
  28 use debuginfo::DebugLoc;
  29 use declare;
  30 use expr;
  31 use glue;
  32 use machine;
  33 use type_::Type;
  34 use type_of::*;
  35 use value::Value;
  36 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
  37
  38 use syntax::ast::Name;
  39 use syntax_pos::DUMMY_SP;
  40
  41 // drop_glue pointer, size, align.
  42 const VTABLE_OFFSET: usize = 3;
  43
  44 /// Extracts a method from a trait object's vtable, at the specified index.
  45 pub fn get_virtual_method<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
  46                                       llvtable: ValueRef,
  47                                       vtable_index: usize)
  48                                       -> ValueRef {
  49     // Load the data pointer from the object.
  50     debug!("get_virtual_method(vtable_index={}, llvtable={:?})",
  51            vtable_index, Value(llvtable));
  52
  53     Load(bcx, GEPi(bcx, llvtable, &[vtable_index + VTABLE_OFFSET]))
  54 }
  55
  56 /// Generate a shim function that allows an object type like `SomeTrait` to
  57 /// implement the type `SomeTrait`. Imagine a trait definition:
  58 ///
  59 ///    trait SomeTrait { fn get(&self) -> i32; ... }
  60 ///
  61 /// And a generic bit of code:
  62 ///
  63 ///    fn foo<T:SomeTrait>(t: &T) {
  64 ///        let x = SomeTrait::get;
  65 ///        x(t)
  66 ///    }
  67 ///
  68 /// What is the value of `x` when `foo` is invoked with `T=SomeTrait`?
  69 /// The answer is that it is a shim function generated by this routine:
  70 ///
  71 ///    fn shim(t: &SomeTrait) -> i32 {
  72 ///        // ... call t.get() virtually ...
  73 ///    }
  74 ///
  75 /// In fact, all virtual calls can be thought of as normal trait calls
  76 /// that go through this shim function.
  77 pub fn trans_object_shim<'a, 'tcx>(ccx: &'a CrateContext<'a, 'tcx>,
  78                                    method_ty: Ty<'tcx>,
  79                                    vtable_index: usize)
  80                                    -> ValueRef {
  81     let _icx = push_ctxt("trans_object_shim");
  82     let tcx = ccx.tcx();
  83
  84     debug!("trans_object_shim(vtable_index={}, method_ty={:?})",
  85            vtable_index,
  86            method_ty);
  87
  88     let sig = tcx.erase_late_bound_regions(&method_ty.fn_sig());
  89     let sig = tcx.normalize_associated_type(&sig);
  90     let fn_ty = FnType::new(ccx, method_ty.fn_abi(), &sig, &[]);
  91
  92     let function_name =
  93         symbol_names::internal_name_from_type_and_suffix(ccx, method_ty, "object_shim");
  94     let llfn = declare::define_internal_fn(ccx, &function_name, method_ty);
  95     attributes::set_frame_pointer_elimination(ccx, llfn);
  96
  97     let (block_arena, fcx): (TypedArena<_>, FunctionContext);
  98     block_arena = TypedArena::new();
  99     fcx = FunctionContext::new(ccx, llfn, fn_ty, None, &block_arena);
 100     let mut bcx = fcx.init(false, None);
 101     assert!(!fcx.needs_ret_allocas);
 102
 103
 104     let dest =
 105         fcx.llretslotptr.get().map(
 106             |_| expr::SaveIn(fcx.get_ret_slot(bcx, "ret_slot")));
 107
 108     debug!("trans_object_shim: method_offset_in_vtable={}",
 109            vtable_index);
 110
 111     let llargs = get_params(fcx.llfn);
 112     let args = ArgVals(&llargs[fcx.fn_ty.ret.is_indirect() as usize..]);
 113
 114     let callee = Callee {
 115         data: Virtual(vtable_index),
 116         ty: method_ty
 117     };
 118     bcx = callee.call(bcx, DebugLoc::None, args, dest).bcx;
 119
 120     fcx.finish(bcx, DebugLoc::None);
 121
 122     llfn
 123 }
 124
 125 /// Creates a returns a dynamic vtable for the given type and vtable origin.
 126 /// This is used only for objects.
 127 ///
 128 /// The `trait_ref` encodes the erased self type. Hence if we are
 129 /// making an object `Foo<Trait>` from a value of type `Foo<T>`, then
 130 /// `trait_ref` would map `T:Trait`.
 131 pub fn get_vtable<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 132                             trait_ref: ty::PolyTraitRef<'tcx>)
 133                             -> ValueRef
 134 {
 135     let tcx = ccx.tcx();
 136     let _icx = push_ctxt("meth::get_vtable");
 137
 138     debug!("get_vtable(trait_ref={:?})", trait_ref);
 139
 140     // Check the cache.
 141     match ccx.vtables().borrow().get(&trait_ref) {
 142         Some(&val) => { return val }
 143         None => { }
 144     }
 145
 146     // Not in the cache. Build it.
 147     let methods = traits::supertraits(tcx, trait_ref.clone()).flat_map(|trait_ref| {
 148         let vtable = fulfill_obligation(ccx.shared(), DUMMY_SP, trait_ref.clone());
 149         match vtable {
 150             // Should default trait error here?
 151             traits::VtableDefaultImpl(_) |
 152             traits::VtableBuiltin(_) => {
 153                 Vec::new().into_iter()
 154             }
 155             traits::VtableImpl(
 156                 traits::VtableImplData {
 157                     impl_def_id: id,
 158                     substs,
 159                     nested: _ }) => {
 160                 let nullptr = C_null(Type::nil(ccx).ptr_to());
 161                 get_vtable_methods(tcx, id, substs)
 162                     .into_iter()
 163                     .map(|opt_mth| opt_mth.map_or(nullptr, |mth| {
 164                         Callee::def(ccx, mth.method.def_id, &mth.substs).reify(ccx).val
 165                     }))
 166                     .collect::<Vec<_>>()
 167                     .into_iter()
 168             }
 169             traits::VtableClosure(
 170                 traits::VtableClosureData {
 171                     closure_def_id,
 172                     substs,
 173                     nested: _ }) => {
 174                 let trait_closure_kind = tcx.lang_items.fn_trait_kind(trait_ref.def_id()).unwrap();
 175                 let llfn = closure::trans_closure_method(ccx,
 176                                                          closure_def_id,
 177                                                          substs,
 178                                                          trait_closure_kind);
 179                 vec![llfn].into_iter()
 180             }
 181             traits::VtableFnPointer(
 182                 traits::VtableFnPointerData {
 183                     fn_ty: bare_fn_ty,
 184                     nested: _ }) => {
 185                 let trait_closure_kind = tcx.lang_items.fn_trait_kind(trait_ref.def_id()).unwrap();
 186                 vec![trans_fn_pointer_shim(ccx, trait_closure_kind, bare_fn_ty)].into_iter()
 187             }
 188             traits::VtableObject(ref data) => {
 189                 // this would imply that the Self type being erased is
 190                 // an object type; this cannot happen because we
 191                 // cannot cast an unsized type into a trait object
 192                 bug!("cannot get vtable for an object type: {:?}",
 193                      data);
 194             }
 195             traits::VtableParam(..) => {
 196                 bug!("resolved vtable for {:?} to bad vtable {:?} in trans",
 197                      trait_ref,
 198                      vtable);
 199             }
 200         }
 201     });
 202
 203     let size_ty = sizing_type_of(ccx, trait_ref.self_ty());
 204     let size = machine::llsize_of_alloc(ccx, size_ty);
 205     let align = align_of(ccx, trait_ref.self_ty());
 206
 207     let components: Vec<_> = vec![
 208         // Generate a destructor for the vtable.
 209         glue::get_drop_glue(ccx, trait_ref.self_ty()),
 210         C_uint(ccx, size),
 211         C_uint(ccx, align)
 212     ].into_iter().chain(methods).collect();
 213
 214     let vtable_const = C_struct(ccx, &components, false);
 215     let align = machine::llalign_of_pref(ccx, val_ty(vtable_const));
 216     let vtable = consts::addr_of(ccx, vtable_const, align, "vtable");
 217
 218     ccx.vtables().borrow_mut().insert(trait_ref, vtable);
 219     vtable
 220 }
 221
 222 pub fn get_vtable_methods<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 223                                     impl_id: DefId,
 224                                     substs: &'tcx subst::Substs<'tcx>)
 225                                     -> Vec<Option<ImplMethod<'tcx>>>
 226 {
 227     debug!("get_vtable_methods(impl_id={:?}, substs={:?}", impl_id, substs);
 228
 229     let trt_id = match tcx.impl_trait_ref(impl_id) {
 230         Some(t_id) => t_id.def_id,
 231         None       => bug!("make_impl_vtable: don't know how to \
 232                             make a vtable for a type impl!")
 233     };
 234
 235     tcx.populate_implementations_for_trait_if_necessary(trt_id);
 236
 237     let trait_item_def_ids = tcx.trait_item_def_ids(trt_id);
 238     trait_item_def_ids
 239         .iter()
 240
 241         // Filter out non-method items.
 242         .filter_map(|item_def_id| {
 243             match *item_def_id {
 244                 ty::MethodTraitItemId(def_id) => Some(def_id),
 245                 _ => None,
 246             }
 247         })
 248
 249         // Now produce pointers for each remaining method. If the
 250         // method could never be called from this object, just supply
 251         // null.
 252         .map(|trait_method_def_id| {
 253             debug!("get_vtable_methods: trait_method_def_id={:?}",
 254                    trait_method_def_id);
 255
 256             let trait_method_type = match tcx.impl_or_trait_item(trait_method_def_id) {
 257                 ty::MethodTraitItem(m) => m,
 258                 _ => bug!("should be a method, not other assoc item"),
 259             };
 260             let name = trait_method_type.name;
 261
 262             // Some methods cannot be called on an object; skip those.
 263             if !tcx.is_vtable_safe_method(trt_id, &trait_method_type) {
 264                 debug!("get_vtable_methods: not vtable safe");
 265                 return None;
 266             }
 267
 268             debug!("get_vtable_methods: trait_method_type={:?}",
 269                    trait_method_type);
 270
 271             // the method may have some early-bound lifetimes, add
 272             // regions for those
 273             let num_dummy_regions = trait_method_type.generics.regions.len(FnSpace);
 274             let dummy_regions = vec![ty::ReErased; num_dummy_regions];
 275             let method_substs = substs.clone()
 276                                       .with_method(vec![], dummy_regions);
 277             let method_substs = tcx.mk_substs(method_substs);
 278
 279             // The substitutions we have are on the impl, so we grab
 280             // the method type from the impl to substitute into.
 281             let mth = get_impl_method(tcx, impl_id, method_substs, name);
 282
 283             debug!("get_vtable_methods: mth={:?}", mth);
 284
 285             // If this is a default method, it's possible that it
 286             // relies on where clauses that do not hold for this
 287             // particular set of type parameters. Note that this
 288             // method could then never be called, so we do not want to
 289             // try and trans it, in that case. Issue #23435.
 290             if mth.is_provided {
 291                 let predicates = mth.method.predicates.predicates.subst(tcx, &mth.substs);
 292                 if !normalize_and_test_predicates(tcx, predicates.into_vec()) {
 293                     debug!("get_vtable_methods: predicates do not hold");
 294                     return None;
 295                 }
 296             }
 297
 298             Some(mth)
 299         })
 300         .collect()
 301 }
 302
 303 #[derive(Debug)]
 304 pub struct ImplMethod<'tcx> {
 305     pub method: Rc<ty::Method<'tcx>>,
 306     pub substs: &'tcx Substs<'tcx>,
 307     pub is_provided: bool
 308 }
 309
 310 /// Locates the applicable definition of a method, given its name.
 311 pub fn get_impl_method<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 312                                  impl_def_id: DefId,
 313                                  substs: &'tcx Substs<'tcx>,
 314                                  name: Name)
 315                                  -> ImplMethod<'tcx>
 316 {
 317     assert!(!substs.types.needs_infer());
 318
 319     let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
 320     let trait_def = tcx.lookup_trait_def(trait_def_id);
 321
 322     match trait_def.ancestors(impl_def_id).fn_defs(tcx, name).next() {
 323         Some(node_item) => {
 324             let substs = tcx.normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
 325                 let substs = traits::translate_substs(&infcx, impl_def_id,
 326                                                       substs, node_item.node);
 327                 tcx.lift(&substs).unwrap_or_else(|| {
 328                     bug!("trans::meth::get_impl_method: translate_substs \
 329                           returned {:?} which contains inference types/regions",
 330                          substs);
 331                 })
 332             });
 333             ImplMethod {
 334                 method: node_item.item,
 335                 substs: substs,
 336                 is_provided: node_item.node.is_from_trait(),
 337             }
 338         }
 339         None => {
 340             bug!("method {:?} not found in {:?}", name, impl_def_id)
 341         }
 342     }
 343 }