src/librustc/middle/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 core::prelude::*;
  12
  13 use back::abi;
  14 use lib::llvm::llvm;
  15 use lib::llvm::ValueRef;
  16 use lib;
  17 use metadata::csearch;
  18 use middle::trans::base::*;
  19 use middle::trans::build::*;
  20 use middle::trans::callee::*;
  21 use middle::trans::callee;
  22 use middle::trans::common::*;
  23 use middle::trans::expr::{SaveIn, Ignore};
  24 use middle::trans::expr;
  25 use middle::trans::glue;
  26 use middle::trans::monomorphize;
  27 use middle::trans::type_of::*;
  28 use middle::ty;
  29 use middle::typeck;
  30 use util::common::indenter;
  31 use util::ppaux::Repr;
  32
  33 use middle::trans::type_::Type;
  34
  35 use core::str;
  36 use core::vec;
  37 use syntax::ast_map::{path, path_mod, path_name};
  38 use syntax::ast_util;
  39 use syntax::{ast, ast_map};
  40
  41 /**
  42 The main "translation" pass for methods.  Generates code
  43 for non-monomorphized methods only.  Other methods will
  44 be generated once they are invoked with specific type parameters,
  45 see `trans::base::lval_static_fn()` or `trans::base::monomorphic_fn()`.
  46 */
  47 pub fn trans_impl(ccx: @mut CrateContext,
  48                   path: path,
  49                   name: ast::ident,
  50                   methods: &[@ast::method],
  51                   generics: &ast::Generics,
  52                   id: ast::node_id) {
  53     let _icx = push_ctxt("impl::trans_impl");
  54     let tcx = ccx.tcx;
  55
  56     debug!("trans_impl(path=%s, name=%s, id=%?)",
  57            path.repr(tcx), name.repr(tcx), id);
  58
  59     if !generics.ty_params.is_empty() { return; }
  60     let sub_path = vec::append_one(path, path_name(name));
  61     for methods.iter().advance |method| {
  62         if method.generics.ty_params.len() == 0u {
  63             let llfn = get_item_val(ccx, method.id);
  64             let path = vec::append_one(/*bad*/copy sub_path,
  65                                        path_name(method.ident));
  66
  67             trans_method(ccx,
  68                          path,
  69                          *method,
  70                          None,
  71                          llfn,
  72                          ast_util::local_def(id));
  73         }
  74     }
  75 }
  76
  77 /**
  78 Translates a (possibly monomorphized) method body.
  79
  80 # Parameters
  81
  82 - `path`: the path to the method
  83 - `method`: the AST node for the method
  84 - `param_substs`: if this is a generic method, the current values for
  85   type parameters and so forth, else none
  86 - `llfn`: the LLVM ValueRef for the method
  87 - `impl_id`: the node ID of the impl this method is inside
  88 */
  89 pub fn trans_method(ccx: @mut CrateContext,
  90                     path: path,
  91                     method: &ast::method,
  92                     param_substs: Option<@param_substs>,
  93                     llfn: ValueRef,
  94                     impl_id: ast::def_id) {
  95     // figure out how self is being passed
  96     let self_arg = match method.explicit_self.node {
  97       ast::sty_static => {
  98         no_self
  99       }
 100       _ => {
 101         // determine the (monomorphized) type that `self` maps to for
 102         // this method
 103         let self_ty = ty::node_id_to_type(ccx.tcx, method.self_id);
 104         let self_ty = match param_substs {
 105             None => self_ty,
 106             Some(@param_substs {tys: ref tys, self_ty: ref self_sub, _}) => {
 107                 ty::subst_tps(ccx.tcx, *tys, *self_sub, self_ty)
 108             }
 109         };
 110         debug!("calling trans_fn with self_ty %s",
 111                self_ty.repr(ccx.tcx));
 112         match method.explicit_self.node {
 113           ast::sty_value => impl_owned_self(self_ty),
 114           _ => {
 115             impl_self(self_ty)
 116           }
 117         }
 118       }
 119     };
 120
 121     // generate the actual code
 122     trans_fn(ccx,
 123              path,
 124              &method.decl,
 125              &method.body,
 126              llfn,
 127              self_arg,
 128              param_substs,
 129              method.id,
 130              Some(impl_id),
 131              []);
 132 }
 133
 134 pub fn trans_self_arg(bcx: block,
 135                       base: @ast::expr,
 136                       mentry: typeck::method_map_entry) -> Result {
 137     let _icx = push_ctxt("impl::trans_self_arg");
 138     let mut temp_cleanups = ~[];
 139
 140     // Compute the type of self.
 141     let self_ty = monomorphize_type(bcx, mentry.self_ty);
 142
 143     let result = trans_arg_expr(bcx,
 144                                 self_ty,
 145                                 mentry.self_mode,
 146                                 mentry.explicit_self,
 147                                 base,
 148                                 &mut temp_cleanups,
 149                                 None,
 150                                 DontAutorefArg);
 151
 152     // FIXME(#3446)---this is wrong, actually.  The temp_cleanups
 153     // should be revoked only after all arguments have been passed.
 154     for temp_cleanups.iter().advance |c| {
 155         revoke_clean(bcx, *c)
 156     }
 157
 158     return result;
 159 }
 160
 161 pub fn trans_method_callee(bcx: block,
 162                            callee_id: ast::node_id,
 163                            this: @ast::expr,
 164                            mentry: typeck::method_map_entry)
 165                            -> Callee {
 166     let _icx = push_ctxt("impl::trans_method_callee");
 167     let tcx = bcx.tcx();
 168
 169     debug!("trans_method_callee(callee_id=%?, this=%s, mentry=%s)",
 170            callee_id,
 171            bcx.expr_to_str(this),
 172            mentry.repr(bcx.tcx()));
 173
 174     // Replace method_self with method_static here.
 175     let mut origin = mentry.origin;
 176     match origin {
 177         typeck::method_self(trait_id, method_index) => {
 178             // Get the ID of the impl we're inside.
 179             let impl_def_id = bcx.fcx.impl_id.get();
 180
 181             debug!("impl_def_id is %?", impl_def_id);
 182
 183             // Get the ID of the method we're calling.
 184             let method_name =
 185                 ty::trait_method(tcx, trait_id, method_index).ident;
 186             let method_id =
 187                 method_with_name_or_default(bcx.ccx(),
 188                                             impl_def_id,
 189                                             method_name);
 190             origin = typeck::method_static(method_id);
 191         }
 192         typeck::method_super(trait_id, method_index) => {
 193             // <self_ty> is the self type for this method call
 194             let self_ty = node_id_type(bcx, this.id);
 195             // <impl_id> is the ID of the implementation of
 196             // trait <trait_id> for type <self_ty>
 197             let impl_id = ty::get_impl_id(tcx, trait_id, self_ty);
 198             // Get the supertrait's methods
 199             let supertrait_method_def_ids = ty::trait_method_def_ids(tcx, trait_id);
 200             // Make sure to fail with a readable error message if
 201             // there's some internal error here
 202             if !(method_index < supertrait_method_def_ids.len()) {
 203                 tcx.sess.bug("trans_method_callee: supertrait method \
 204                               index is out of bounds");
 205             }
 206             // Get the method name using the method index in the origin
 207             let method_name =
 208                 ty::method(tcx, supertrait_method_def_ids[method_index]).ident;
 209             // Now that we know the impl ID, we can look up the method
 210             // ID from its name
 211             origin = typeck::method_static(
 212                 method_with_name_or_default(bcx.ccx(),
 213                                             impl_id,
 214                                             method_name));
 215         }
 216         typeck::method_static(*) | typeck::method_param(*) |
 217         typeck::method_trait(*) => {}
 218     }
 219
 220     debug!("origin=%?", origin);
 221
 222     match origin {
 223         typeck::method_static(did) => {
 224             let callee_fn = callee::trans_fn_ref(bcx, did, callee_id);
 225             let Result {bcx, val} = trans_self_arg(bcx, this, mentry);
 226             Callee {
 227                 bcx: bcx,
 228                 data: Method(MethodData {
 229                     llfn: callee_fn.llfn,
 230                     llself: val,
 231                     self_ty: node_id_type(bcx, this.id),
 232                     self_mode: mentry.self_mode,
 233                     explicit_self: mentry.explicit_self
 234                 })
 235             }
 236         }
 237         typeck::method_param(typeck::method_param {
 238             trait_id: trait_id,
 239             method_num: off,
 240             param_num: p,
 241             bound_num: b
 242         }) => {
 243             match bcx.fcx.param_substs {
 244                 Some(substs) => {
 245                     let vtbl = find_vtable(bcx.tcx(), substs, p, b);
 246                     trans_monomorphized_callee(bcx, callee_id, this, mentry,
 247                                                trait_id, off, vtbl)
 248                 }
 249                 // how to get rid of this?
 250                 None => fail!("trans_method_callee: missing param_substs")
 251             }
 252         }
 253         typeck::method_trait(_, off, store) => {
 254             trans_trait_callee(bcx,
 255                                callee_id,
 256                                off,
 257                                this,
 258                                store,
 259                                mentry.explicit_self)
 260         }
 261         typeck::method_self(*) | typeck::method_super(*) => {
 262             fail!("method_self or method_super should have been handled \
 263                 above")
 264         }
 265     }
 266 }
 267
 268 pub fn trans_static_method_callee(bcx: block,
 269                                   method_id: ast::def_id,
 270                                   trait_id: ast::def_id,
 271                                   callee_id: ast::node_id)
 272                                -> FnData {
 273     let _icx = push_ctxt("impl::trans_static_method_callee");
 274     let ccx = bcx.ccx();
 275
 276     debug!("trans_static_method_callee(method_id=%?, trait_id=%s, \
 277             callee_id=%?)",
 278            method_id,
 279            ty::item_path_str(bcx.tcx(), trait_id),
 280            callee_id);
 281     let _indenter = indenter();
 282
 283     // When we translate a static fn defined in a trait like:
 284     //
 285     //   trait<T1...Tn> Trait {
 286     //       fn foo<M1...Mn>(...) {...}
 287     //   }
 288     //
 289     // this winds up being translated as something like:
 290     //
 291     //   fn foo<T1...Tn,self: Trait<T1...Tn>,M1...Mn>(...) {...}
 292     //
 293     // So when we see a call to this function foo, we have to figure
 294     // out which impl the `Trait<T1...Tn>` bound on the type `self` was
 295     // bound to.  Due to the fact that we use a flattened list of
 296     // impls, one per bound, this means we have to total up the bounds
 297     // found on the type parametesr T1...Tn to find the index of the
 298     // one we are interested in.
 299     let bound_index = {
 300         let trait_def = ty::lookup_trait_def(bcx.tcx(), trait_id);
 301         ty::count_traits_and_supertraits(
 302             bcx.tcx(), *trait_def.generics.type_param_defs)
 303     };
 304
 305     let mname = if method_id.crate == ast::local_crate {
 306         match bcx.tcx().items.get_copy(&method_id.node) {
 307             ast_map::node_trait_method(trait_method, _, _) => {
 308                 ast_util::trait_method_to_ty_method(trait_method).ident
 309             }
 310             _ => fail!("callee is not a trait method")
 311         }
 312     } else {
 313         let path = csearch::get_item_path(bcx.tcx(), method_id);
 314         match path[path.len()-1] {
 315             path_name(s) => { s }
 316             path_mod(_) => { fail!("path doesn't have a name?") }
 317         }
 318     };
 319     debug!("trans_static_method_callee: method_id=%?, callee_id=%?, \
 320             name=%s", method_id, callee_id, ccx.sess.str_of(mname));
 321
 322     let vtbls = resolve_vtables_in_fn_ctxt(
 323         bcx.fcx, ccx.maps.vtable_map.get_copy(&callee_id));
 324
 325     match vtbls[bound_index] {
 326         typeck::vtable_static(impl_did, ref rcvr_substs, rcvr_origins) => {
 327             assert!(rcvr_substs.iter().all(|t| !ty::type_needs_infer(*t)));
 328
 329             let mth_id = method_with_name_or_default(bcx.ccx(),
 330                                                      impl_did,
 331                                                      mname);
 332             let callee_substs = combine_impl_and_methods_tps(
 333                 bcx, mth_id, impl_did, callee_id, *rcvr_substs);
 334             let callee_origins = combine_impl_and_methods_origins(
 335                 bcx, mth_id, impl_did, callee_id, rcvr_origins);
 336
 337             let FnData {llfn: lval} =
 338                 trans_fn_ref_with_vtables(bcx,
 339                                           mth_id,
 340                                           callee_id,
 341                                           callee_substs,
 342                                           Some(callee_origins));
 343
 344             let callee_ty = node_id_type(bcx, callee_id);
 345             let llty = type_of_fn_from_ty(ccx, callee_ty).ptr_to();
 346             FnData {llfn: PointerCast(bcx, lval, llty)}
 347         }
 348         _ => {
 349             fail!("vtable_param left in monomorphized \
 350                    function's vtable substs");
 351         }
 352     }
 353 }
 354
 355 pub fn method_from_methods(ms: &[@ast::method], name: ast::ident)
 356     -> Option<ast::def_id> {
 357     ms.iter().find_(|m| m.ident == name).map(|m| ast_util::local_def(m.id))
 358 }
 359
 360 pub fn method_with_name_or_default(ccx: &mut CrateContext,
 361                                    impl_id: ast::def_id,
 362                                    name: ast::ident) -> ast::def_id {
 363     let imp = ccx.impl_method_cache.find_copy(&(impl_id, name));
 364     match imp {
 365         Some(m) => return m,
 366         None => {}
 367     }
 368
 369     // None of this feels like it should be the best way to do this.
 370     let mut did = if impl_id.crate == ast::local_crate {
 371         match ccx.tcx.items.get_copy(&impl_id.node) {
 372             ast_map::node_item(@ast::item {
 373                 node: ast::item_impl(_, _, _, ref ms), _
 374             }, _) => { method_from_methods(*ms, name) },
 375             _ => fail!("method_with_name")
 376         }
 377     } else {
 378         csearch::get_impl_method(ccx.sess.cstore, impl_id, name)
 379     };
 380
 381     if did.is_none() {
 382         // Look for a default method
 383         let pmm = ccx.tcx.provided_methods;
 384         match pmm.find(&impl_id) {
 385             Some(pmis) => {
 386                 for pmis.iter().advance |pmi| {
 387                     if pmi.method_info.ident == name {
 388                         debug!("pmi.method_info.did = %?",
 389                                pmi.method_info.did);
 390                         did = Some(pmi.method_info.did);
 391                     }
 392                 }
 393             }
 394             None => {}
 395         }
 396     }
 397
 398     let imp = did.expect("could not find method while translating");
 399     ccx.impl_method_cache.insert((impl_id, name), imp);
 400     imp
 401 }
 402
 403 pub fn method_ty_param_count(ccx: &CrateContext, m_id: ast::def_id,
 404                              i_id: ast::def_id) -> uint {
 405     debug!("method_ty_param_count: m_id: %?, i_id: %?", m_id, i_id);
 406     ty::method(ccx.tcx, m_id).generics.type_param_defs.len()
 407 }
 408
 409 pub fn trans_monomorphized_callee(bcx: block,
 410                                   callee_id: ast::node_id,
 411                                   base: @ast::expr,
 412                                   mentry: typeck::method_map_entry,
 413                                   trait_id: ast::def_id,
 414                                   n_method: uint,
 415                                   vtbl: typeck::vtable_origin)
 416                                   -> Callee {
 417     let _icx = push_ctxt("impl::trans_monomorphized_callee");
 418     return match vtbl {
 419       typeck::vtable_static(impl_did, ref rcvr_substs, rcvr_origins) => {
 420           let ccx = bcx.ccx();
 421           let mname = ty::trait_method(ccx.tcx, trait_id, n_method).ident;
 422           let mth_id = method_with_name_or_default(
 423               bcx.ccx(), impl_did, mname);
 424
 425           // obtain the `self` value:
 426           let Result {bcx, val: llself_val} =
 427               trans_self_arg(bcx, base, mentry);
 428
 429           // create a concatenated set of substitutions which includes
 430           // those from the impl and those from the method:
 431           let callee_substs = combine_impl_and_methods_tps(
 432               bcx, mth_id, impl_did, callee_id, *rcvr_substs);
 433           let callee_origins = combine_impl_and_methods_origins(
 434               bcx, mth_id, impl_did, callee_id, rcvr_origins);
 435
 436           // translate the function
 437           let callee = trans_fn_ref_with_vtables(bcx,
 438                                                  mth_id,
 439                                                  callee_id,
 440                                                  callee_substs,
 441                                                  Some(callee_origins));
 442
 443           // create a llvalue that represents the fn ptr
 444           let fn_ty = node_id_type(bcx, callee_id);
 445           let llfn_ty = type_of_fn_from_ty(ccx, fn_ty).ptr_to();
 446           let llfn_val = PointerCast(bcx, callee.llfn, llfn_ty);
 447
 448           // combine the self environment with the rest
 449           Callee {
 450               bcx: bcx,
 451               data: Method(MethodData {
 452                   llfn: llfn_val,
 453                   llself: llself_val,
 454                   self_ty: node_id_type(bcx, base.id),
 455                   self_mode: mentry.self_mode,
 456                   explicit_self: mentry.explicit_self
 457               })
 458           }
 459       }
 460       typeck::vtable_param(*) => {
 461           fail!("vtable_param left in monomorphized function's vtable substs");
 462       }
 463     };
 464
 465 }
 466
 467 pub fn combine_impl_and_methods_tps(bcx: block,
 468                                     mth_did: ast::def_id,
 469                                     impl_did: ast::def_id,
 470                                     callee_id: ast::node_id,
 471                                     rcvr_substs: &[ty::t])
 472                                     -> ~[ty::t] {
 473     /*!
 474     *
 475     * Creates a concatenated set of substitutions which includes
 476     * those from the impl and those from the method.  This are
 477     * some subtle complications here.  Statically, we have a list
 478     * of type parameters like `[T0, T1, T2, M1, M2, M3]` where
 479     * `Tn` are type parameters that appear on the receiver.  For
 480     * example, if the receiver is a method parameter `A` with a
 481     * bound like `trait<B,C,D>` then `Tn` would be `[B,C,D]`.
 482     *
 483     * The weird part is that the type `A` might now be bound to
 484     * any other type, such as `foo<X>`.  In that case, the vector
 485     * we want is: `[X, M1, M2, M3]`.  Therefore, what we do now is
 486     * to slice off the method type parameters and append them to
 487     * the type parameters from the type that the receiver is
 488     * mapped to. */
 489
 490     let ccx = bcx.ccx();
 491     let n_m_tps = method_ty_param_count(ccx, mth_did, impl_did);
 492     let node_substs = node_id_type_params(bcx, callee_id);
 493     debug!("rcvr_substs=%?", rcvr_substs.map(|t| bcx.ty_to_str(*t)));
 494     let ty_substs
 495         = vec::append(rcvr_substs.to_owned(),
 496                       node_substs.tailn(node_substs.len() - n_m_tps));
 497     debug!("n_m_tps=%?", n_m_tps);
 498     debug!("node_substs=%?", node_substs.map(|t| bcx.ty_to_str(*t)));
 499     debug!("ty_substs=%?", ty_substs.map(|t| bcx.ty_to_str(*t)));
 500
 501     return ty_substs;
 502 }
 503
 504 pub fn combine_impl_and_methods_origins(bcx: block,
 505                                         mth_did: ast::def_id,
 506                                         impl_did: ast::def_id,
 507                                         callee_id: ast::node_id,
 508                                         rcvr_origins: typeck::vtable_res)
 509                                      -> typeck::vtable_res {
 510     /*!
 511      *
 512      * Similar to `combine_impl_and_methods_tps`, but for vtables.
 513      * This is much messier because of the flattened layout we are
 514      * currently using (for some reason that I fail to understand).
 515      * The proper fix is described in #3446.
 516      */
 517
 518
 519     // Find the bounds for the method, which are the tail of the
 520     // bounds found in the item type, as the item type combines the
 521     // rcvr + method bounds.
 522     let ccx = bcx.ccx();
 523     let tcx = bcx.tcx();
 524     let n_m_tps = method_ty_param_count(ccx, mth_did, impl_did);
 525     let ty::ty_param_bounds_and_ty {
 526         generics: r_m_generics,
 527         _
 528     } = ty::lookup_item_type(tcx, mth_did);
 529     let n_r_m_tps = r_m_generics.type_param_defs.len(); // rcvr + method tps
 530     let m_type_param_defs =
 531         r_m_generics.type_param_defs.slice(n_r_m_tps - n_m_tps, n_r_m_tps);
 532
 533     // Flatten out to find the number of vtables the method expects.
 534     let m_vtables = ty::count_traits_and_supertraits(tcx, m_type_param_defs);
 535
 536     // Find the vtables we computed at type check time and monomorphize them
 537     let r_m_origins = match node_vtables(bcx, callee_id) {
 538         Some(vt) => vt,
 539         None => @~[]
 540     };
 541
 542     // Extract those that belong to method:
 543     let m_origins = r_m_origins.tailn(r_m_origins.len() - m_vtables);
 544
 545     // Combine rcvr + method to find the final result:
 546     @vec::append(/*bad*/copy *rcvr_origins, m_origins)
 547 }
 548
 549
 550 pub fn trans_trait_callee(bcx: block,
 551                           callee_id: ast::node_id,
 552                           n_method: uint,
 553                           self_expr: @ast::expr,
 554                           store: ty::TraitStore,
 555                           explicit_self: ast::explicit_self_)
 556                        -> Callee {
 557     //!
 558     //
 559     // Create a method callee where the method is coming from a trait
 560     // instance (e.g., @Trait type).  In this case, we must pull the
 561     // fn pointer out of the vtable that is packaged up with the
 562     // @/~/&Trait instance.  @/~/&Traits are represented as a pair, so we
 563     // first evaluate the self expression (expected a by-ref result) and then
 564     // extract the self data and vtable out of the pair.
 565
 566     let _icx = push_ctxt("impl::trans_trait_callee");
 567     let mut bcx = bcx;
 568     let self_datum = unpack_datum!(bcx,
 569         expr::trans_to_datum(bcx, self_expr));
 570     let llpair = self_datum.to_ref_llval(bcx);
 571
 572     let llpair = match explicit_self {
 573         ast::sty_region(*) => Load(bcx, llpair),
 574         ast::sty_static | ast::sty_value |
 575         ast::sty_box(_) | ast::sty_uniq(_) => llpair
 576     };
 577
 578     let callee_ty = node_id_type(bcx, callee_id);
 579     trans_trait_callee_from_llval(bcx,
 580                                   callee_ty,
 581                                   n_method,
 582                                   llpair,
 583                                   store,
 584                                   explicit_self)
 585 }
 586
 587 pub fn trans_trait_callee_from_llval(bcx: block,
 588                                      callee_ty: ty::t,
 589                                      n_method: uint,
 590                                      llpair: ValueRef,
 591                                      store: ty::TraitStore,
 592                                      explicit_self: ast::explicit_self_)
 593                                   -> Callee {
 594     //!
 595     //
 596     // Same as `trans_trait_callee()` above, except that it is given
 597     // a by-ref pointer to the @Trait pair.
 598
 599     let _icx = push_ctxt("impl::trans_trait_callee");
 600     let ccx = bcx.ccx();
 601     let mut bcx = bcx;
 602
 603     // Load the vtable from the @Trait pair
 604     debug!("(translating trait callee) loading vtable from pair %s",
 605            bcx.val_to_str(llpair));
 606     let llvtable = Load(bcx,
 607                       PointerCast(bcx,
 608                                   GEPi(bcx, llpair,
 609                                        [0u, abi::trt_field_vtable]),
 610                                   Type::vtable().ptr_to().ptr_to()));
 611
 612     // Load the box from the @Trait pair and GEP over the box header if
 613     // necessary:
 614     let mut llself;
 615     debug!("(translating trait callee) loading second index from pair");
 616     let llbox = Load(bcx, GEPi(bcx, llpair, [0u, abi::trt_field_box]));
 617
 618     // Munge `llself` appropriately for the type of `self` in the method.
 619     let self_mode;
 620     match explicit_self {
 621         ast::sty_static => {
 622             bcx.tcx().sess.bug("shouldn't see static method here");
 623         }
 624         ast::sty_value => {
 625             bcx.tcx().sess.bug("methods with by-value self should not be \
 626                                 called on objects");
 627         }
 628         ast::sty_region(*) => {
 629             // As before, we need to pass a pointer to a pointer to the
 630             // payload.
 631             match store {
 632                 ty::BoxTraitStore |
 633                 ty::UniqTraitStore => {
 634                     llself = GEPi(bcx, llbox, [0u, abi::box_field_body]);
 635                 }
 636                 ty::RegionTraitStore(_) => {
 637                     llself = llbox;
 638                 }
 639             }
 640
 641             let llscratch = alloca(bcx, val_ty(llself));
 642             Store(bcx, llself, llscratch);
 643             llself = llscratch;
 644
 645             self_mode = ty::ByRef;
 646         }
 647         ast::sty_box(_) => {
 648             // Bump the reference count on the box.
 649             debug!("(translating trait callee) callee type is `%s`",
 650                    bcx.ty_to_str(callee_ty));
 651             bcx = glue::take_ty(bcx, llbox, callee_ty);
 652
 653             // Pass a pointer to the box.
 654             match store {
 655                 ty::BoxTraitStore => llself = llbox,
 656                 _ => bcx.tcx().sess.bug("@self receiver with non-@Trait")
 657             }
 658
 659             let llscratch = alloca(bcx, val_ty(llself));
 660             Store(bcx, llself, llscratch);
 661             llself = llscratch;
 662
 663             self_mode = ty::ByRef;
 664         }
 665         ast::sty_uniq(_) => {
 666             // Pass the unique pointer.
 667             match store {
 668                 ty::UniqTraitStore => llself = llbox,
 669                 _ => bcx.tcx().sess.bug("~self receiver with non-~Trait")
 670             }
 671
 672             let llscratch = alloca(bcx, val_ty(llself));
 673             Store(bcx, llself, llscratch);
 674             llself = llscratch;
 675
 676             self_mode = ty::ByRef;
 677         }
 678     }
 679
 680     // Load the function from the vtable and cast it to the expected type.
 681     debug!("(translating trait callee) loading method");
 682     let llcallee_ty = type_of_fn_from_ty(ccx, callee_ty);
 683
 684     // Plus one in order to skip past the type descriptor.
 685     let mptr = Load(bcx, GEPi(bcx, llvtable, [0u, n_method + 1]));
 686
 687     let mptr = PointerCast(bcx, mptr, llcallee_ty.ptr_to());
 688
 689     return Callee {
 690         bcx: bcx,
 691         data: Method(MethodData {
 692             llfn: mptr,
 693             llself: llself,
 694             self_ty: ty::mk_opaque_box(bcx.tcx()),
 695             self_mode: self_mode,
 696             explicit_self: explicit_self
 697             /* XXX: Some(llbox) */
 698         })
 699     };
 700 }
 701
 702 pub fn vtable_id(ccx: @mut CrateContext,
 703                  origin: &typeck::vtable_origin)
 704               -> mono_id {
 705     match origin {
 706         &typeck::vtable_static(impl_id, ref substs, sub_vtables) => {
 707             monomorphize::make_mono_id(
 708                 ccx,
 709                 impl_id,
 710                 *substs,
 711                 if sub_vtables.is_empty() {
 712                     None
 713                 } else {
 714                     Some(sub_vtables)
 715                 },
 716                 None,
 717                 None)
 718         }
 719
 720         // can't this be checked at the callee?
 721         _ => fail!("vtable_id")
 722     }
 723 }
 724
 725 /// Creates a returns a dynamic vtable for the given type and vtable origin.
 726 /// This is used only for objects.
 727 pub fn get_vtable(bcx: block,
 728                   self_ty: ty::t,
 729                   origin: typeck::vtable_origin)
 730                   -> ValueRef {
 731     let hash_id = vtable_id(bcx.ccx(), &origin);
 732     match bcx.ccx().vtables.find(&hash_id) {
 733         Some(&val) => val,
 734         None => {
 735             match origin {
 736                 typeck::vtable_static(id, substs, sub_vtables) => {
 737                     make_impl_vtable(bcx, id, self_ty, substs, sub_vtables)
 738                 }
 739                 _ => fail!("get_vtable: expected a static origin"),
 740             }
 741         }
 742     }
 743 }
 744
 745 /// Helper function to declare and initialize the vtable.
 746 pub fn make_vtable(ccx: &mut CrateContext,
 747                    tydesc: &tydesc_info,
 748                    ptrs: &[ValueRef])
 749                    -> ValueRef {
 750     unsafe {
 751         let _icx = push_ctxt("impl::make_vtable");
 752
 753         let mut components = ~[ tydesc.tydesc ];
 754         for ptrs.iter().advance |&ptr| {
 755             components.push(ptr)
 756         }
 757
 758         let tbl = C_struct(components);
 759         let vtable = ccx.sess.str_of((ccx.names)("vtable"));
 760         let vt_gvar = do str::as_c_str(vtable) |buf| {
 761             llvm::LLVMAddGlobal(ccx.llmod, val_ty(tbl).to_ref(), buf)
 762         };
 763         llvm::LLVMSetInitializer(vt_gvar, tbl);
 764         llvm::LLVMSetGlobalConstant(vt_gvar, lib::llvm::True);
 765         lib::llvm::SetLinkage(vt_gvar, lib::llvm::InternalLinkage);
 766         vt_gvar
 767     }
 768 }
 769
 770 /// Generates a dynamic vtable for objects.
 771 pub fn make_impl_vtable(bcx: block,
 772                         impl_id: ast::def_id,
 773                         self_ty: ty::t,
 774                         substs: &[ty::t],
 775                         vtables: typeck::vtable_res)
 776                         -> ValueRef {
 777     let ccx = bcx.ccx();
 778     let _icx = push_ctxt("impl::make_impl_vtable");
 779     let tcx = ccx.tcx;
 780
 781     let trt_id = match ty::impl_trait_ref(tcx, impl_id) {
 782         Some(t_id) => t_id.def_id,
 783         None       => ccx.sess.bug("make_impl_vtable: don't know how to \
 784                                     make a vtable for a type impl!")
 785     };
 786
 787     let trait_method_def_ids = ty::trait_method_def_ids(tcx, trt_id);
 788     let methods = do trait_method_def_ids.map |method_def_id| {
 789         let im = ty::method(tcx, *method_def_id);
 790         let fty = ty::subst_tps(tcx,
 791                                 substs,
 792                                 None,
 793                                 ty::mk_bare_fn(tcx, copy im.fty));
 794         if im.generics.has_type_params() || ty::type_has_self(fty) {
 795             debug!("(making impl vtable) method has self or type params: %s",
 796                    tcx.sess.str_of(im.ident));
 797             C_null(Type::nil().ptr_to())
 798         } else {
 799             debug!("(making impl vtable) adding method to vtable: %s",
 800                    tcx.sess.str_of(im.ident));
 801             let m_id = method_with_name_or_default(ccx, impl_id, im.ident);
 802
 803             trans_fn_ref_with_vtables(bcx, m_id, 0,
 804                                       substs, Some(vtables)).llfn
 805         }
 806     };
 807
 808     // Generate a type descriptor for the vtable.
 809     let tydesc = get_tydesc(ccx, self_ty);
 810     glue::lazily_emit_all_tydesc_glue(ccx, tydesc);
 811
 812     make_vtable(ccx, tydesc, methods)
 813 }
 814
 815 pub fn trans_trait_cast(bcx: block,
 816                         val: @ast::expr,
 817                         id: ast::node_id,
 818                         dest: expr::Dest,
 819                         _store: ty::TraitStore)
 820                      -> block {
 821     let mut bcx = bcx;
 822     let _icx = push_ctxt("impl::trans_cast");
 823
 824     let lldest = match dest {
 825         Ignore => {
 826             return expr::trans_into(bcx, val, Ignore);
 827         }
 828         SaveIn(dest) => dest
 829     };
 830
 831     let ccx = bcx.ccx();
 832     let v_ty = expr_ty(bcx, val);
 833
 834     let mut llboxdest = GEPi(bcx, lldest, [0u, abi::trt_field_box]);
 835     // Just store the pointer into the pair. (Region/borrowed
 836     // and boxed trait objects are represented as pairs, and
 837     // have no type descriptor field.)
 838     llboxdest = PointerCast(bcx,
 839                             llboxdest,
 840                             type_of(bcx.ccx(), v_ty).ptr_to());
 841     bcx = expr::trans_into(bcx, val, SaveIn(llboxdest));
 842
 843     // Store the vtable into the pair or triple.
 844     let orig = /*bad*/copy ccx.maps.vtable_map.get(&id)[0];
 845     let orig = resolve_vtable_in_fn_ctxt(bcx.fcx, orig);
 846     let vtable = get_vtable(bcx, v_ty, orig);
 847     Store(bcx, vtable, PointerCast(bcx,
 848                                    GEPi(bcx, lldest, [0u, abi::trt_field_vtable]),
 849                                    val_ty(vtable).ptr_to()));
 850
 851     bcx
 852 }