src/librustc/middle/trans/expr.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 /*!
  12  * # Translation of Expressions
  13  *
  14  * Public entry points:
  15  *
  16  * - `trans_into(bcx, expr, dest) -> bcx`: evaluates an expression,
  17  *   storing the result into `dest`. This is the preferred form, if you
  18  *   can manage it.
  19  *
  20  * - `trans(bcx, expr) -> DatumBlock`: evaluates an expression, yielding
  21  *   `Datum` with the result. You can then store the datum, inspect
  22  *   the value, etc. This may introduce temporaries if the datum is a
  23  *   structural type.
  24  *
  25  * - `trans_to_lvalue(bcx, expr, "...") -> DatumBlock`: evaluates an
  26  *   expression and ensures that the result has a cleanup associated with it,
  27  *   creating a temporary stack slot if necessary.
  28  *
  29  * - `trans_local_var -> Datum`: looks up a local variable or upvar.
  30  *
  31  * See doc.rs for more comments.
  32  */
  33
  34 #![allow(non_camel_case_types)]
  35
  36 use back::abi;
  37 use lib::llvm::{ValueRef, llvm};
  38 use lib;
  39 use metadata::csearch;
  40 use middle::def;
  41 use middle::lang_items::MallocFnLangItem;
  42 use middle::mem_categorization::Typer;
  43 use middle::trans::_match;
  44 use middle::trans::adt;
  45 use middle::trans::asm;
  46 use middle::trans::base::*;
  47 use middle::trans::base;
  48 use middle::trans::build::*;
  49 use middle::trans::callee;
  50 use middle::trans::cleanup;
  51 use middle::trans::cleanup::CleanupMethods;
  52 use middle::trans::closure;
  53 use middle::trans::common::*;
  54 use middle::trans::consts;
  55 use middle::trans::controlflow;
  56 use middle::trans::datum::*;
  57 use middle::trans::debuginfo;
  58 use middle::trans::glue;
  59 use middle::trans::machine;
  60 use middle::trans::meth;
  61 use middle::trans::inline;
  62 use middle::trans::tvec;
  63 use middle::trans::type_of;
  64 use middle::ty::struct_fields;
  65 use middle::ty::{AutoBorrowObj, AutoDerefRef, AutoAddEnv, AutoObject, AutoUnsafe};
  66 use middle::ty::{AutoPtr, AutoBorrowVec, AutoBorrowVecRef};
  67 use middle::ty;
  68 use middle::typeck;
  69 use middle::typeck::MethodCall;
  70 use util::common::indenter;
  71 use util::ppaux::Repr;
  72 use util::nodemap::NodeMap;
  73 use middle::trans::machine::{llalign_of_min, llsize_of, llsize_of_alloc};
  74 use middle::trans::type_::Type;
  75
  76 use syntax::ast;
  77 use syntax::codemap;
  78 use syntax::print::pprust::{expr_to_str};
  79
  80 use std::gc::Gc;
  81
  82 // Destinations
  83
  84 // These are passed around by the code generating functions to track the
  85 // destination of a computation's value.
  86
  87 #[deriving(PartialEq)]
  88 pub enum Dest {
  89     SaveIn(ValueRef),
  90     Ignore,
  91 }
  92
  93 impl Dest {
  94     pub fn to_str(&self, ccx: &CrateContext) -> String {
  95         match *self {
  96             SaveIn(v) => format!("SaveIn({})", ccx.tn.val_to_str(v)),
  97             Ignore => "Ignore".to_string()
  98         }
  99     }
 100 }
 101
 102 pub fn trans_into<'a>(bcx: &'a Block<'a>,
 103                       expr: &ast::Expr,
 104                       dest: Dest)
 105                       -> &'a Block<'a> {
 106     /*!
 107      * This function is equivalent to `trans(bcx, expr).store_to_dest(dest)`
 108      * but it may generate better optimized LLVM code.
 109      */
 110
 111     let mut bcx = bcx;
 112
 113     if bcx.tcx().adjustments.borrow().contains_key(&expr.id) {
 114         // use trans, which may be less efficient but
 115         // which will perform the adjustments:
 116         let datum = unpack_datum!(bcx, trans(bcx, expr));
 117         return datum.store_to_dest(bcx, dest, expr.id)
 118     }
 119
 120     debug!("trans_into() expr={}", expr.repr(bcx.tcx()));
 121     debuginfo::set_source_location(bcx.fcx, expr.id, expr.span);
 122
 123     bcx.fcx.push_ast_cleanup_scope(expr.id);
 124
 125     let kind = ty::expr_kind(bcx.tcx(), expr);
 126     bcx = match kind {
 127         ty::LvalueExpr | ty::RvalueDatumExpr => {
 128             trans_unadjusted(bcx, expr).store_to_dest(dest, expr.id)
 129         }
 130         ty::RvalueDpsExpr => {
 131             trans_rvalue_dps_unadjusted(bcx, expr, dest)
 132         }
 133         ty::RvalueStmtExpr => {
 134             trans_rvalue_stmt_unadjusted(bcx, expr)
 135         }
 136     };
 137
 138     bcx.fcx.pop_and_trans_ast_cleanup_scope(bcx, expr.id)
 139 }
 140
 141 pub fn trans<'a>(bcx: &'a Block<'a>,
 142                  expr: &ast::Expr)
 143                  -> DatumBlock<'a, Expr> {
 144     /*!
 145      * Translates an expression, returning a datum (and new block)
 146      * encapsulating the result. When possible, it is preferred to
 147      * use `trans_into`, as that may avoid creating a temporary on
 148      * the stack.
 149      */
 150
 151     debug!("trans(expr={})", bcx.expr_to_str(expr));
 152
 153     let mut bcx = bcx;
 154     let fcx = bcx.fcx;
 155
 156     fcx.push_ast_cleanup_scope(expr.id);
 157     let datum = unpack_datum!(bcx, trans_unadjusted(bcx, expr));
 158     let datum = unpack_datum!(bcx, apply_adjustments(bcx, expr, datum));
 159     bcx = fcx.pop_and_trans_ast_cleanup_scope(bcx, expr.id);
 160     return DatumBlock::new(bcx, datum);
 161 }
 162
 163 fn apply_adjustments<'a>(bcx: &'a Block<'a>,
 164                          expr: &ast::Expr,
 165                          datum: Datum<Expr>)
 166                          -> DatumBlock<'a, Expr> {
 167     /*!
 168      * Helper for trans that apply adjustments from `expr` to `datum`,
 169      * which should be the unadjusted translation of `expr`.
 170      */
 171
 172     let mut bcx = bcx;
 173     let mut datum = datum;
 174     let adjustment = match bcx.tcx().adjustments.borrow().find_copy(&expr.id) {
 175         None => {
 176             return DatumBlock::new(bcx, datum);
 177         }
 178         Some(adj) => { adj }
 179     };
 180     debug!("unadjusted datum for expr {}: {}",
 181            expr.id, datum.to_str(bcx.ccx()));
 182     match adjustment {
 183         AutoAddEnv(..) => {
 184             datum = unpack_datum!(bcx, add_env(bcx, expr, datum));
 185         }
 186         AutoDerefRef(ref adj) => {
 187             if adj.autoderefs > 0 {
 188                 datum = unpack_datum!(
 189                     bcx, deref_multiple(bcx, expr, datum, adj.autoderefs));
 190             }
 191
 192             datum = match adj.autoref {
 193                 None => {
 194                     datum
 195                 }
 196                 Some(AutoUnsafe(..)) | // region + unsafe ptrs have same repr
 197                 Some(AutoPtr(..)) => {
 198                     unpack_datum!(bcx, auto_ref(bcx, datum, expr))
 199                 }
 200                 Some(AutoBorrowVec(..)) => {
 201                     unpack_datum!(bcx, auto_slice(bcx, expr, datum))
 202                 }
 203                 Some(AutoBorrowVecRef(..)) => {
 204                     unpack_datum!(bcx, auto_slice_and_ref(bcx, expr, datum))
 205                 }
 206                 Some(AutoBorrowObj(..)) => {
 207                     unpack_datum!(bcx, auto_borrow_obj(bcx, expr, datum))
 208                 }
 209             };
 210         }
 211         AutoObject(..) => {
 212             let adjusted_ty = ty::expr_ty_adjusted(bcx.tcx(), expr);
 213             let scratch = rvalue_scratch_datum(bcx, adjusted_ty, "__adjust");
 214             bcx = meth::trans_trait_cast(
 215                 bcx, datum, expr.id, SaveIn(scratch.val));
 216             datum = scratch.to_expr_datum();
 217         }
 218     }
 219     debug!("after adjustments, datum={}", datum.to_str(bcx.ccx()));
 220     return DatumBlock {bcx: bcx, datum: datum};
 221
 222     fn auto_slice<'a>(
 223                   bcx: &'a Block<'a>,
 224                   expr: &ast::Expr,
 225                   datum: Datum<Expr>)
 226                   -> DatumBlock<'a, Expr> {
 227         // This is not the most efficient thing possible; since slices
 228         // are two words it'd be better if this were compiled in
 229         // 'dest' mode, but I can't find a nice way to structure the
 230         // code and keep it DRY that accommodates that use case at the
 231         // moment.
 232
 233         let mut bcx = bcx;
 234         let tcx = bcx.tcx();
 235         let unit_ty = ty::sequence_element_type(tcx, datum.ty);
 236
 237         // Arrange cleanup, if not already done. This is needed in
 238         // case we are auto-slicing an owned vector or some such.
 239         let datum = unpack_datum!(
 240             bcx, datum.to_lvalue_datum(bcx, "auto_slice", expr.id));
 241
 242         let (base, len) = datum.get_vec_base_and_len(bcx);
 243
 244         // this type may have a different region/mutability than the
 245         // real one, but it will have the same runtime representation
 246         let slice_ty = ty::mk_slice(tcx, ty::ReStatic,
 247                                     ty::mt { ty: unit_ty, mutbl: ast::MutImmutable });
 248
 249         let scratch = rvalue_scratch_datum(bcx, slice_ty, "__adjust");
 250         Store(bcx, base, GEPi(bcx, scratch.val, [0u, abi::slice_elt_base]));
 251         Store(bcx, len, GEPi(bcx, scratch.val, [0u, abi::slice_elt_len]));
 252         DatumBlock::new(bcx, scratch.to_expr_datum())
 253     }
 254
 255     fn add_env<'a>(bcx: &'a Block<'a>,
 256                    expr: &ast::Expr,
 257                    datum: Datum<Expr>)
 258                    -> DatumBlock<'a, Expr> {
 259         // This is not the most efficient thing possible; since closures
 260         // are two words it'd be better if this were compiled in
 261         // 'dest' mode, but I can't find a nice way to structure the
 262         // code and keep it DRY that accommodates that use case at the
 263         // moment.
 264
 265         let closure_ty = expr_ty_adjusted(bcx, expr);
 266         let fn_ptr = datum.to_llscalarish(bcx);
 267         let def = ty::resolve_expr(bcx.tcx(), expr);
 268         closure::make_closure_from_bare_fn(bcx, closure_ty, def, fn_ptr)
 269     }
 270
 271     fn auto_slice_and_ref<'a>(
 272                           bcx: &'a Block<'a>,
 273                           expr: &ast::Expr,
 274                           datum: Datum<Expr>)
 275                           -> DatumBlock<'a, Expr> {
 276         let DatumBlock { bcx, datum } = auto_slice(bcx, expr, datum);
 277         auto_ref(bcx, datum, expr)
 278     }
 279
 280     fn auto_borrow_obj<'a>(bcx: &'a Block<'a>,
 281                            expr: &ast::Expr,
 282                            source_datum: Datum<Expr>)
 283                            -> DatumBlock<'a, Expr> {
 284         let tcx = bcx.tcx();
 285         let target_obj_ty = expr_ty_adjusted(bcx, expr);
 286         debug!("auto_borrow_obj(target={})", target_obj_ty.repr(tcx));
 287
 288         let mut datum = source_datum.to_expr_datum();
 289         datum.ty = target_obj_ty;
 290         DatumBlock::new(bcx, datum)
 291     }
 292 }
 293
 294 pub fn trans_to_lvalue<'a>(bcx: &'a Block<'a>,
 295                            expr: &ast::Expr,
 296                            name: &str)
 297                            -> DatumBlock<'a, Lvalue> {
 298     /*!
 299      * Translates an expression in "lvalue" mode -- meaning that it
 300      * returns a reference to the memory that the expr represents.
 301      *
 302      * If this expression is an rvalue, this implies introducing a
 303      * temporary.  In other words, something like `x().f` is
 304      * translated into roughly the equivalent of
 305      *
 306      *   { tmp = x(); tmp.f }
 307      */
 308
 309     let mut bcx = bcx;
 310     let datum = unpack_datum!(bcx, trans(bcx, expr));
 311     return datum.to_lvalue_datum(bcx, name, expr.id);
 312 }
 313
 314 fn trans_unadjusted<'a>(bcx: &'a Block<'a>,
 315                         expr: &ast::Expr)
 316                         -> DatumBlock<'a, Expr> {
 317     /*!
 318      * A version of `trans` that ignores adjustments. You almost
 319      * certainly do not want to call this directly.
 320      */
 321
 322     let mut bcx = bcx;
 323
 324     debug!("trans_unadjusted(expr={})", bcx.expr_to_str(expr));
 325     let _indenter = indenter();
 326
 327     debuginfo::set_source_location(bcx.fcx, expr.id, expr.span);
 328
 329     return match ty::expr_kind(bcx.tcx(), expr) {
 330         ty::LvalueExpr | ty::RvalueDatumExpr => {
 331             let datum = unpack_datum!(bcx, {
 332                 trans_datum_unadjusted(bcx, expr)
 333             });
 334
 335             DatumBlock {bcx: bcx, datum: datum}
 336         }
 337
 338         ty::RvalueStmtExpr => {
 339             bcx = trans_rvalue_stmt_unadjusted(bcx, expr);
 340             nil(bcx, expr_ty(bcx, expr))
 341         }
 342
 343         ty::RvalueDpsExpr => {
 344             let ty = expr_ty(bcx, expr);
 345             if type_is_zero_size(bcx.ccx(), ty) {
 346                 bcx = trans_rvalue_dps_unadjusted(bcx, expr, Ignore);
 347                 nil(bcx, ty)
 348             } else {
 349                 let scratch = rvalue_scratch_datum(bcx, ty, "");
 350                 bcx = trans_rvalue_dps_unadjusted(
 351                     bcx, expr, SaveIn(scratch.val));
 352
 353                 // Note: this is not obviously a good idea.  It causes
 354                 // immediate values to be loaded immediately after a
 355                 // return from a call or other similar expression,
 356                 // which in turn leads to alloca's having shorter
 357                 // lifetimes and hence larger stack frames.  However,
 358                 // in turn it can lead to more register pressure.
 359                 // Still, in practice it seems to increase
 360                 // performance, since we have fewer problems with
 361                 // morestack churn.
 362                 let scratch = unpack_datum!(
 363                     bcx, scratch.to_appropriate_datum(bcx));
 364
 365                 DatumBlock::new(bcx, scratch.to_expr_datum())
 366             }
 367         }
 368     };
 369
 370     fn nil<'a>(bcx: &'a Block<'a>, ty: ty::t) -> DatumBlock<'a, Expr> {
 371         let llval = C_undef(type_of::type_of(bcx.ccx(), ty));
 372         let datum = immediate_rvalue(llval, ty);
 373         DatumBlock::new(bcx, datum.to_expr_datum())
 374     }
 375 }
 376
 377 fn trans_datum_unadjusted<'a>(bcx: &'a Block<'a>,
 378                               expr: &ast::Expr)
 379                               -> DatumBlock<'a, Expr> {
 380     let mut bcx = bcx;
 381     let fcx = bcx.fcx;
 382     let _icx = push_ctxt("trans_datum_unadjusted");
 383
 384     match expr.node {
 385         ast::ExprParen(ref e) => {
 386             trans(bcx, &**e)
 387         }
 388         ast::ExprPath(_) => {
 389             trans_def(bcx, expr, bcx.def(expr.id))
 390         }
 391         ast::ExprField(ref base, ident, _) => {
 392             trans_rec_field(bcx, &**base, ident.node)
 393         }
 394         ast::ExprIndex(ref base, ref idx) => {
 395             trans_index(bcx, expr, &**base, &**idx)
 396         }
 397         ast::ExprVstore(ref contents, ast::ExprVstoreUniq) => {
 398             fcx.push_ast_cleanup_scope(contents.id);
 399             let datum = unpack_datum!(
 400                 bcx, tvec::trans_uniq_vstore(bcx, expr, &**contents));
 401             bcx = fcx.pop_and_trans_ast_cleanup_scope(bcx, contents.id);
 402             DatumBlock::new(bcx, datum)
 403         }
 404         ast::ExprBox(_, ref contents) => {
 405             // Special case for `Box<T>` and `Gc<T>`
 406             let box_ty = expr_ty(bcx, expr);
 407             let contents_ty = expr_ty(bcx, &**contents);
 408             match ty::get(box_ty).sty {
 409                 ty::ty_uniq(..) => {
 410                     trans_uniq_expr(bcx, box_ty, &**contents, contents_ty)
 411                 }
 412                 ty::ty_box(..) => {
 413                     trans_managed_expr(bcx, box_ty, &**contents, contents_ty)
 414                 }
 415                 _ => bcx.sess().span_bug(expr.span,
 416                                          "expected unique or managed box")
 417             }
 418         }
 419         ast::ExprLit(ref lit) => trans_immediate_lit(bcx, expr, (**lit).clone()),
 420         ast::ExprBinary(op, ref lhs, ref rhs) => {
 421             trans_binary(bcx, expr, op, &**lhs, &**rhs)
 422         }
 423         ast::ExprUnary(op, ref x) => {
 424             trans_unary(bcx, expr, op, &**x)
 425         }
 426         ast::ExprAddrOf(_, ref x) => {
 427             trans_addr_of(bcx, expr, &**x)
 428         }
 429         ast::ExprCast(ref val, _) => {
 430             // Datum output mode means this is a scalar cast:
 431             trans_imm_cast(bcx, &**val, expr.id)
 432         }
 433         _ => {
 434             bcx.tcx().sess.span_bug(
 435                 expr.span,
 436                 format!("trans_rvalue_datum_unadjusted reached \
 437                          fall-through case: {:?}",
 438                         expr.node).as_slice());
 439         }
 440     }
 441 }
 442
 443 fn trans_rec_field<'a>(bcx: &'a Block<'a>,
 444                        base: &ast::Expr,
 445                        field: ast::Ident)
 446                        -> DatumBlock<'a, Expr> {
 447     //! Translates `base.field`.
 448
 449     let mut bcx = bcx;
 450     let _icx = push_ctxt("trans_rec_field");
 451
 452     let base_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, base, "field"));
 453     let repr = adt::represent_type(bcx.ccx(), base_datum.ty);
 454     with_field_tys(bcx.tcx(), base_datum.ty, None, |discr, field_tys| {
 455             let ix = ty::field_idx_strict(bcx.tcx(), field.name, field_tys);
 456             let d = base_datum.get_element(
 457                 field_tys[ix].mt.ty,
 458                 |srcval| adt::trans_field_ptr(bcx, &*repr, srcval, discr, ix));
 459             DatumBlock { datum: d.to_expr_datum(), bcx: bcx }
 460         })
 461 }
 462
 463 fn trans_index<'a>(bcx: &'a Block<'a>,
 464                    index_expr: &ast::Expr,
 465                    base: &ast::Expr,
 466                    idx: &ast::Expr)
 467                    -> DatumBlock<'a, Expr> {
 468     //! Translates `base[idx]`.
 469
 470     let _icx = push_ctxt("trans_index");
 471     let ccx = bcx.ccx();
 472     let mut bcx = bcx;
 473
 474     let base_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, base, "index"));
 475
 476     // Translate index expression and cast to a suitable LLVM integer.
 477     // Rust is less strict than LLVM in this regard.
 478     let ix_datum = unpack_datum!(bcx, trans(bcx, idx));
 479     let ix_val = ix_datum.to_llscalarish(bcx);
 480     let ix_size = machine::llbitsize_of_real(bcx.ccx(), val_ty(ix_val));
 481     let int_size = machine::llbitsize_of_real(bcx.ccx(), ccx.int_type);
 482     let ix_val = {
 483         if ix_size < int_size {
 484             if ty::type_is_signed(expr_ty(bcx, idx)) {
 485                 SExt(bcx, ix_val, ccx.int_type)
 486             } else { ZExt(bcx, ix_val, ccx.int_type) }
 487         } else if ix_size > int_size {
 488             Trunc(bcx, ix_val, ccx.int_type)
 489         } else {
 490             ix_val
 491         }
 492     };
 493
 494     let vt = tvec::vec_types(bcx, ty::sequence_element_type(bcx.tcx(), base_datum.ty));
 495     base::maybe_name_value(bcx.ccx(), vt.llunit_size, "unit_sz");
 496
 497     let (base, len) = base_datum.get_vec_base_and_len(bcx);
 498
 499     debug!("trans_index: base {}", bcx.val_to_str(base));
 500     debug!("trans_index: len {}", bcx.val_to_str(len));
 501
 502     let bounds_check = ICmp(bcx, lib::llvm::IntUGE, ix_val, len);
 503     let expect = ccx.get_intrinsic(&("llvm.expect.i1"));
 504     let expected = Call(bcx, expect, [bounds_check, C_i1(ccx, false)], []);
 505     let bcx = with_cond(bcx, expected, |bcx| {
 506             controlflow::trans_fail_bounds_check(bcx, index_expr.span, ix_val, len)
 507         });
 508     let elt = InBoundsGEP(bcx, base, [ix_val]);
 509     let elt = PointerCast(bcx, elt, vt.llunit_ty.ptr_to());
 510     DatumBlock::new(bcx, Datum::new(elt, vt.unit_ty, LvalueExpr))
 511 }
 512
 513 fn trans_def<'a>(bcx: &'a Block<'a>,
 514                  ref_expr: &ast::Expr,
 515                  def: def::Def)
 516                  -> DatumBlock<'a, Expr>
 517 {
 518     //! Translates a reference to a path.
 519
 520     let _icx = push_ctxt("trans_def_lvalue");
 521     match def {
 522         def::DefFn(..) | def::DefStaticMethod(..) |
 523         def::DefStruct(_) | def::DefVariant(..) => {
 524             trans_def_fn_unadjusted(bcx, ref_expr, def)
 525         }
 526         def::DefStatic(did, _) => {
 527             let const_ty = expr_ty(bcx, ref_expr);
 528
 529             fn get_did(ccx: &CrateContext, did: ast::DefId)
 530                        -> ast::DefId {
 531                 if did.krate != ast::LOCAL_CRATE {
 532                     inline::maybe_instantiate_inline(ccx, did)
 533                 } else {
 534                     did
 535                 }
 536             }
 537
 538             fn get_val<'a>(bcx: &'a Block<'a>, did: ast::DefId, const_ty: ty::t)
 539                        -> ValueRef {
 540                 // For external constants, we don't inline.
 541                 if did.krate == ast::LOCAL_CRATE {
 542                     // The LLVM global has the type of its initializer,
 543                     // which may not be equal to the enum's type for
 544                     // non-C-like enums.
 545                     let val = base::get_item_val(bcx.ccx(), did.node);
 546                     let pty = type_of::type_of(bcx.ccx(), const_ty).ptr_to();
 547                     PointerCast(bcx, val, pty)
 548                 } else {
 549                     match bcx.ccx().extern_const_values.borrow().find(&did) {
 550                         None => {}  // Continue.
 551                         Some(llval) => {
 552                             return *llval;
 553                         }
 554                     }
 555
 556                     unsafe {
 557                         let llty = type_of::type_of(bcx.ccx(), const_ty);
 558                         let symbol = csearch::get_symbol(
 559                             &bcx.ccx().sess().cstore,
 560                             did);
 561                         let llval = symbol.as_slice().with_c_str(|buf| {
 562                                 llvm::LLVMAddGlobal(bcx.ccx().llmod,
 563                                                     llty.to_ref(),
 564                                                     buf)
 565                             });
 566                         bcx.ccx().extern_const_values.borrow_mut()
 567                            .insert(did, llval);
 568                         llval
 569                     }
 570                 }
 571             }
 572
 573             let did = get_did(bcx.ccx(), did);
 574             let val = get_val(bcx, did, const_ty);
 575             DatumBlock::new(bcx, Datum::new(val, const_ty, LvalueExpr))
 576         }
 577         _ => {
 578             DatumBlock::new(bcx, trans_local_var(bcx, def).to_expr_datum())
 579         }
 580     }
 581 }
 582
 583 fn trans_rvalue_stmt_unadjusted<'a>(bcx: &'a Block<'a>,
 584                                     expr: &ast::Expr)
 585                                     -> &'a Block<'a> {
 586     let mut bcx = bcx;
 587     let _icx = push_ctxt("trans_rvalue_stmt");
 588
 589     if bcx.unreachable.get() {
 590         return bcx;
 591     }
 592
 593     match expr.node {
 594         ast::ExprParen(ref e) => {
 595             trans_into(bcx, &**e, Ignore)
 596         }
 597         ast::ExprBreak(label_opt) => {
 598             controlflow::trans_break(bcx, expr.id, label_opt)
 599         }
 600         ast::ExprAgain(label_opt) => {
 601             controlflow::trans_cont(bcx, expr.id, label_opt)
 602         }
 603         ast::ExprRet(ex) => {
 604             controlflow::trans_ret(bcx, ex)
 605         }
 606         ast::ExprWhile(ref cond, ref body) => {
 607             controlflow::trans_while(bcx, expr.id, &**cond, &**body)
 608         }
 609         ast::ExprLoop(ref body, _) => {
 610             controlflow::trans_loop(bcx, expr.id, &**body)
 611         }
 612         ast::ExprAssign(ref dst, ref src) => {
 613             let dst_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, &**dst, "assign"));
 614
 615             if ty::type_needs_drop(bcx.tcx(), dst_datum.ty) {
 616                 // If there are destructors involved, make sure we
 617                 // are copying from an rvalue, since that cannot possible
 618                 // alias an lvalue. We are concerned about code like:
 619                 //
 620                 //   a = a
 621                 //
 622                 // but also
 623                 //
 624                 //   a = a.b
 625                 //
 626                 // where e.g. a : Option<Foo> and a.b :
 627                 // Option<Foo>. In that case, freeing `a` before the
 628                 // assignment may also free `a.b`!
 629                 //
 630                 // We could avoid this intermediary with some analysis
 631                 // to determine whether `dst` may possibly own `src`.
 632                 let src_datum = unpack_datum!(bcx, trans(bcx, &**src));
 633                 let src_datum = unpack_datum!(
 634                     bcx, src_datum.to_rvalue_datum(bcx, "ExprAssign"));
 635                 bcx = glue::drop_ty(bcx, dst_datum.val, dst_datum.ty);
 636                 src_datum.store_to(bcx, dst_datum.val)
 637             } else {
 638                 trans_into(bcx, &**src, SaveIn(dst_datum.to_llref()))
 639             }
 640         }
 641         ast::ExprAssignOp(op, ref dst, ref src) => {
 642             trans_assign_op(bcx, expr, op, &**dst, src.clone())
 643         }
 644         ast::ExprInlineAsm(ref a) => {
 645             asm::trans_inline_asm(bcx, a)
 646         }
 647         _ => {
 648             bcx.tcx().sess.span_bug(
 649                 expr.span,
 650                 format!("trans_rvalue_stmt_unadjusted reached \
 651                          fall-through case: {:?}",
 652                         expr.node).as_slice());
 653         }
 654     }
 655 }
 656
 657 fn trans_rvalue_dps_unadjusted<'a>(bcx: &'a Block<'a>,
 658                                    expr: &ast::Expr,
 659                                    dest: Dest)
 660                                    -> &'a Block<'a> {
 661     let _icx = push_ctxt("trans_rvalue_dps_unadjusted");
 662     let mut bcx = bcx;
 663     let tcx = bcx.tcx();
 664     let fcx = bcx.fcx;
 665
 666     match expr.node {
 667         ast::ExprParen(ref e) => {
 668             trans_into(bcx, &**e, dest)
 669         }
 670         ast::ExprPath(_) => {
 671             trans_def_dps_unadjusted(bcx, expr, bcx.def(expr.id), dest)
 672         }
 673         ast::ExprIf(ref cond, ref thn, els) => {
 674             controlflow::trans_if(bcx, expr.id, &**cond, thn.clone(), els, dest)
 675         }
 676         ast::ExprMatch(ref discr, ref arms) => {
 677             _match::trans_match(bcx, expr, &**discr, arms.as_slice(), dest)
 678         }
 679         ast::ExprBlock(ref blk) => {
 680             controlflow::trans_block(bcx, &**blk, dest)
 681         }
 682         ast::ExprStruct(_, ref fields, base) => {
 683             trans_rec_or_struct(bcx,
 684                                 fields.as_slice(),
 685                                 base,
 686                                 expr.span,
 687                                 expr.id,
 688                                 dest)
 689         }
 690         ast::ExprTup(ref args) => {
 691             let repr = adt::represent_type(bcx.ccx(), expr_ty(bcx, expr));
 692             let numbered_fields: Vec<(uint, Gc<ast::Expr>)> =
 693                 args.iter().enumerate().map(|(i, arg)| (i, *arg)).collect();
 694             trans_adt(bcx, &*repr, 0, numbered_fields.as_slice(), None, dest)
 695         }
 696         ast::ExprLit(lit) => {
 697             match lit.node {
 698                 ast::LitStr(ref s, _) => {
 699                     tvec::trans_lit_str(bcx, expr, (*s).clone(), dest)
 700                 }
 701                 _ => {
 702                     bcx.tcx()
 703                        .sess
 704                        .span_bug(expr.span,
 705                                  "trans_rvalue_dps_unadjusted shouldn't be \
 706                                   translating this type of literal")
 707                 }
 708             }
 709         }
 710         ast::ExprVstore(ref contents, ast::ExprVstoreSlice) |
 711         ast::ExprVstore(ref contents, ast::ExprVstoreMutSlice) => {
 712             fcx.push_ast_cleanup_scope(contents.id);
 713             bcx = tvec::trans_slice_vstore(bcx, expr, &**contents, dest);
 714             fcx.pop_and_trans_ast_cleanup_scope(bcx, contents.id)
 715         }
 716         ast::ExprVec(..) | ast::ExprRepeat(..) => {
 717             tvec::trans_fixed_vstore(bcx, expr, expr, dest)
 718         }
 719         ast::ExprFnBlock(ref decl, ref body) |
 720         ast::ExprProc(ref decl, ref body) => {
 721             let expr_ty = expr_ty(bcx, expr);
 722             let store = ty::ty_closure_store(expr_ty);
 723             debug!("translating block function {} with type {}",
 724                    expr_to_str(expr), expr_ty.repr(tcx));
 725             closure::trans_expr_fn(bcx, store, &**decl, &**body, expr.id, dest)
 726         }
 727         ast::ExprCall(ref f, ref args) => {
 728             if bcx.tcx().is_method_call(expr.id) {
 729                 let callee_datum = unpack_datum!(bcx, trans(bcx, &**f));
 730                 trans_overloaded_call(bcx,
 731                                       expr,
 732                                       callee_datum,
 733                                       args.as_slice(),
 734                                       Some(dest))
 735             } else {
 736                 callee::trans_call(bcx,
 737                                    expr,
 738                                    &**f,
 739                                    callee::ArgExprs(args.as_slice()),
 740                                    dest)
 741             }
 742         }
 743         ast::ExprMethodCall(_, _, ref args) => {
 744             callee::trans_method_call(bcx,
 745                                       expr,
 746                                       &**args.get(0),
 747                                       callee::ArgExprs(args.as_slice()),
 748                                       dest)
 749         }
 750         ast::ExprBinary(_, ref lhs, ref rhs) => {
 751             // if not overloaded, would be RvalueDatumExpr
 752             let lhs = unpack_datum!(bcx, trans(bcx, &**lhs));
 753             let rhs_datum = unpack_datum!(bcx, trans(bcx, &**rhs));
 754             trans_overloaded_op(bcx, expr, MethodCall::expr(expr.id), lhs,
 755                                 Some((rhs_datum, rhs.id)), Some(dest)).bcx
 756         }
 757         ast::ExprUnary(_, ref subexpr) => {
 758             // if not overloaded, would be RvalueDatumExpr
 759             let arg = unpack_datum!(bcx, trans(bcx, &**subexpr));
 760             trans_overloaded_op(bcx, expr, MethodCall::expr(expr.id),
 761                                 arg, None, Some(dest)).bcx
 762         }
 763         ast::ExprIndex(ref base, ref idx) => {
 764             // if not overloaded, would be RvalueDatumExpr
 765             let base = unpack_datum!(bcx, trans(bcx, &**base));
 766             let idx_datum = unpack_datum!(bcx, trans(bcx, &**idx));
 767             trans_overloaded_op(bcx, expr, MethodCall::expr(expr.id), base,
 768                                 Some((idx_datum, idx.id)), Some(dest)).bcx
 769         }
 770         ast::ExprCast(ref val, _) => {
 771             // DPS output mode means this is a trait cast:
 772             if ty::type_is_trait(node_id_type(bcx, expr.id)) {
 773                 let datum = unpack_datum!(bcx, trans(bcx, &**val));
 774                 meth::trans_trait_cast(bcx, datum, expr.id, dest)
 775             } else {
 776                 bcx.tcx().sess.span_bug(expr.span,
 777                                         "expr_cast of non-trait");
 778             }
 779         }
 780         ast::ExprAssignOp(op, ref dst, ref src) => {
 781             trans_assign_op(bcx, expr, op, &**dst, src.clone())
 782         }
 783         _ => {
 784             bcx.tcx().sess.span_bug(
 785                 expr.span,
 786                 format!("trans_rvalue_dps_unadjusted reached fall-through \
 787                          case: {:?}",
 788                         expr.node).as_slice());
 789         }
 790     }
 791 }
 792
 793 fn trans_def_dps_unadjusted<'a>(
 794                             bcx: &'a Block<'a>,
 795                             ref_expr: &ast::Expr,
 796                             def: def::Def,
 797                             dest: Dest)
 798                             -> &'a Block<'a> {
 799     let _icx = push_ctxt("trans_def_dps_unadjusted");
 800
 801     let lldest = match dest {
 802         SaveIn(lldest) => lldest,
 803         Ignore => { return bcx; }
 804     };
 805
 806     match def {
 807         def::DefVariant(tid, vid, _) => {
 808             let variant_info = ty::enum_variant_with_id(bcx.tcx(), tid, vid);
 809             if variant_info.args.len() > 0u {
 810                 // N-ary variant.
 811                 let llfn = callee::trans_fn_ref(bcx, vid, ExprId(ref_expr.id));
 812                 Store(bcx, llfn, lldest);
 813                 return bcx;
 814             } else {
 815                 // Nullary variant.
 816                 let ty = expr_ty(bcx, ref_expr);
 817                 let repr = adt::represent_type(bcx.ccx(), ty);
 818                 adt::trans_start_init(bcx, &*repr, lldest,
 819                                       variant_info.disr_val);
 820                 return bcx;
 821             }
 822         }
 823         def::DefStruct(_) => {
 824             let ty = expr_ty(bcx, ref_expr);
 825             match ty::get(ty).sty {
 826                 ty::ty_struct(did, _) if ty::has_dtor(bcx.tcx(), did) => {
 827                     let repr = adt::represent_type(bcx.ccx(), ty);
 828                     adt::trans_start_init(bcx, &*repr, lldest, 0);
 829                 }
 830                 _ => {}
 831             }
 832             bcx
 833         }
 834         _ => {
 835             bcx.tcx().sess.span_bug(ref_expr.span, format!(
 836                 "Non-DPS def {:?} referened by {}",
 837                 def, bcx.node_id_to_str(ref_expr.id)).as_slice());
 838         }
 839     }
 840 }
 841
 842 fn trans_def_fn_unadjusted<'a>(bcx: &'a Block<'a>,
 843                                ref_expr: &ast::Expr,
 844                                def: def::Def) -> DatumBlock<'a, Expr> {
 845     let _icx = push_ctxt("trans_def_datum_unadjusted");
 846
 847     let llfn = match def {
 848         def::DefFn(did, _) |
 849         def::DefStruct(did) | def::DefVariant(_, did, _) |
 850         def::DefStaticMethod(did, def::FromImpl(_), _) => {
 851             callee::trans_fn_ref(bcx, did, ExprId(ref_expr.id))
 852         }
 853         def::DefStaticMethod(impl_did, def::FromTrait(trait_did), _) => {
 854             meth::trans_static_method_callee(bcx, impl_did,
 855                                              trait_did, ref_expr.id)
 856         }
 857         _ => {
 858             bcx.tcx().sess.span_bug(ref_expr.span, format!(
 859                     "trans_def_fn_unadjusted invoked on: {:?} for {}",
 860                     def,
 861                     ref_expr.repr(bcx.tcx())).as_slice());
 862         }
 863     };
 864
 865     let fn_ty = expr_ty(bcx, ref_expr);
 866     DatumBlock::new(bcx, Datum::new(llfn, fn_ty, RvalueExpr(Rvalue::new(ByValue))))
 867 }
 868
 869 pub fn trans_local_var<'a>(bcx: &'a Block<'a>,
 870                            def: def::Def)
 871                            -> Datum<Lvalue> {
 872     /*!
 873      * Translates a reference to a local variable or argument.
 874      * This always results in an lvalue datum.
 875      */
 876
 877     let _icx = push_ctxt("trans_local_var");
 878
 879     return match def {
 880         def::DefUpvar(nid, _, _, _) => {
 881             // Can't move upvars, so this is never a ZeroMemLastUse.
 882             let local_ty = node_id_type(bcx, nid);
 883             match bcx.fcx.llupvars.borrow().find(&nid) {
 884                 Some(&val) => Datum::new(val, local_ty, Lvalue),
 885                 None => {
 886                     bcx.sess().bug(format!(
 887                         "trans_local_var: no llval for upvar {:?} found",
 888                         nid).as_slice());
 889                 }
 890             }
 891         }
 892         def::DefArg(nid, _) => {
 893             take_local(bcx, &*bcx.fcx.llargs.borrow(), nid)
 894         }
 895         def::DefLocal(nid, _) | def::DefBinding(nid, _) => {
 896             take_local(bcx, &*bcx.fcx.lllocals.borrow(), nid)
 897         }
 898         _ => {
 899             bcx.sess().unimpl(format!(
 900                 "unsupported def type in trans_local_var: {:?}",
 901                 def).as_slice());
 902         }
 903     };
 904
 905     fn take_local<'a>(bcx: &'a Block<'a>,
 906                       table: &NodeMap<Datum<Lvalue>>,
 907                       nid: ast::NodeId)
 908                       -> Datum<Lvalue> {
 909         let datum = match table.find(&nid) {
 910             Some(&v) => v,
 911             None => {
 912                 bcx.sess().bug(format!(
 913                     "trans_local_var: no datum for local/arg {:?} found",
 914                     nid).as_slice());
 915             }
 916         };
 917         debug!("take_local(nid={:?}, v={}, ty={})",
 918                nid, bcx.val_to_str(datum.val), bcx.ty_to_str(datum.ty));
 919         datum
 920     }
 921 }
 922
 923 pub fn with_field_tys<R>(tcx: &ty::ctxt,
 924                          ty: ty::t,
 925                          node_id_opt: Option<ast::NodeId>,
 926                          op: |ty::Disr, (&[ty::field])| -> R)
 927                          -> R {
 928     /*!
 929      * Helper for enumerating the field types of structs, enums, or records.
 930      * The optional node ID here is the node ID of the path identifying the enum
 931      * variant in use. If none, this cannot possibly an enum variant (so, if it
 932      * is and `node_id_opt` is none, this function fails).
 933      */
 934
 935     match ty::get(ty).sty {
 936         ty::ty_struct(did, ref substs) => {
 937             op(0, struct_fields(tcx, did, substs).as_slice())
 938         }
 939
 940         ty::ty_enum(_, ref substs) => {
 941             // We want the *variant* ID here, not the enum ID.
 942             match node_id_opt {
 943                 None => {
 944                     tcx.sess.bug(format!(
 945                         "cannot get field types from the enum type {} \
 946                          without a node ID",
 947                         ty.repr(tcx)).as_slice());
 948                 }
 949                 Some(node_id) => {
 950                     let def = tcx.def_map.borrow().get_copy(&node_id);
 951                     match def {
 952                         def::DefVariant(enum_id, variant_id, _) => {
 953                             let variant_info = ty::enum_variant_with_id(
 954                                 tcx, enum_id, variant_id);
 955                             op(variant_info.disr_val,
 956                                struct_fields(tcx,
 957                                              variant_id,
 958                                              substs).as_slice())
 959                         }
 960                         _ => {
 961                             tcx.sess.bug("resolve didn't map this expr to a \
 962                                           variant ID")
 963                         }
 964                     }
 965                 }
 966             }
 967         }
 968
 969         _ => {
 970             tcx.sess.bug(format!(
 971                 "cannot get field types from the type {}",
 972                 ty.repr(tcx)).as_slice());
 973         }
 974     }
 975 }
 976
 977 fn trans_rec_or_struct<'a>(
 978                        bcx: &'a Block<'a>,
 979                        fields: &[ast::Field],
 980                        base: Option<Gc<ast::Expr>>,
 981                        expr_span: codemap::Span,
 982                        id: ast::NodeId,
 983                        dest: Dest)
 984                        -> &'a Block<'a> {
 985     let _icx = push_ctxt("trans_rec");
 986     let bcx = bcx;
 987
 988     let ty = node_id_type(bcx, id);
 989     let tcx = bcx.tcx();
 990     with_field_tys(tcx, ty, Some(id), |discr, field_tys| {
 991         let mut need_base = Vec::from_elem(field_tys.len(), true);
 992
 993         let numbered_fields = fields.iter().map(|field| {
 994             let opt_pos =
 995                 field_tys.iter().position(|field_ty|
 996                                           field_ty.ident.name == field.ident.node.name);
 997             match opt_pos {
 998                 Some(i) => {
 999                     *need_base.get_mut(i) = false;
1000                     (i, field.expr)
1001                 }
1002                 None => {
1003                     tcx.sess.span_bug(field.span,
1004                                       "Couldn't find field in struct type")
1005                 }
1006             }
1007         }).collect::<Vec<_>>();
1008         let optbase = match base {
1009             Some(base_expr) => {
1010                 let mut leftovers = Vec::new();
1011                 for (i, b) in need_base.iter().enumerate() {
1012                     if *b {
1013                         leftovers.push((i, field_tys[i].mt.ty))
1014                     }
1015                 }
1016                 Some(StructBaseInfo {expr: base_expr,
1017                                      fields: leftovers })
1018             }
1019             None => {
1020                 if need_base.iter().any(|b| *b) {
1021                     tcx.sess.span_bug(expr_span, "missing fields and no base expr")
1022                 }
1023                 None
1024             }
1025         };
1026
1027         let repr = adt::represent_type(bcx.ccx(), ty);
1028         trans_adt(bcx, &*repr, discr, numbered_fields.as_slice(), optbase, dest)
1029     })
1030 }
1031
1032 /**
1033  * Information that `trans_adt` needs in order to fill in the fields
1034  * of a struct copied from a base struct (e.g., from an expression
1035  * like `Foo { a: b, ..base }`.
1036  *
1037  * Note that `fields` may be empty; the base expression must always be
1038  * evaluated for side-effects.
1039  */
1040 struct StructBaseInfo {
1041     /// The base expression; will be evaluated after all explicit fields.
1042     expr: Gc<ast::Expr>,
1043     /// The indices of fields to copy paired with their types.
1044     fields: Vec<(uint, ty::t)> }
1045
1046 /**
1047  * Constructs an ADT instance:
1048  *
1049  * - `fields` should be a list of field indices paired with the
1050  * expression to store into that field.  The initializers will be
1051  * evaluated in the order specified by `fields`.
1052  *
1053  * - `optbase` contains information on the base struct (if any) from
1054  * which remaining fields are copied; see comments on `StructBaseInfo`.
1055  */
1056 fn trans_adt<'a>(
1057              bcx: &'a Block<'a>,
1058              repr: &adt::Repr,
1059              discr: ty::Disr,
1060              fields: &[(uint, Gc<ast::Expr>)],
1061              optbase: Option<StructBaseInfo>,
1062              dest: Dest)
1063              -> &'a Block<'a> {
1064     let _icx = push_ctxt("trans_adt");
1065     let fcx = bcx.fcx;
1066     let mut bcx = bcx;
1067     let addr = match dest {
1068         Ignore => {
1069             for &(_i, ref e) in fields.iter() {
1070                 bcx = trans_into(bcx, &**e, Ignore);
1071             }
1072             for sbi in optbase.iter() {
1073                 // FIXME #7261: this moves entire base, not just certain fields
1074                 bcx = trans_into(bcx, &*sbi.expr, Ignore);
1075             }
1076             return bcx;
1077         }
1078         SaveIn(pos) => pos
1079     };
1080
1081     // This scope holds intermediates that must be cleaned should
1082     // failure occur before the ADT as a whole is ready.
1083     let custom_cleanup_scope = fcx.push_custom_cleanup_scope();
1084
1085     adt::trans_start_init(bcx, repr, addr, discr);
1086
1087     for &(i, ref e) in fields.iter() {
1088         let dest = adt::trans_field_ptr(bcx, repr, addr, discr, i);
1089         let e_ty = expr_ty_adjusted(bcx, &**e);
1090         bcx = trans_into(bcx, &**e, SaveIn(dest));
1091         fcx.schedule_drop_mem(cleanup::CustomScope(custom_cleanup_scope),
1092                               dest, e_ty);
1093     }
1094
1095     for base in optbase.iter() {
1096         // FIXME #6573: is it sound to use the destination's repr on the base?
1097         // And, would it ever be reasonable to be here with discr != 0?
1098         let base_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, &*base.expr, "base"));
1099         for &(i, t) in base.fields.iter() {
1100             let datum = base_datum.get_element(
1101                 t,
1102                 |srcval| adt::trans_field_ptr(bcx, repr, srcval, discr, i));
1103             let dest = adt::trans_field_ptr(bcx, repr, addr, discr, i);
1104             bcx = datum.store_to(bcx, dest);
1105         }
1106     }
1107
1108     fcx.pop_custom_cleanup_scope(custom_cleanup_scope);
1109
1110     return bcx;
1111 }
1112
1113
1114 fn trans_immediate_lit<'a>(bcx: &'a Block<'a>,
1115                            expr: &ast::Expr,
1116                            lit: ast::Lit)
1117                            -> DatumBlock<'a, Expr> {
1118     // must not be a string constant, that is a RvalueDpsExpr
1119     let _icx = push_ctxt("trans_immediate_lit");
1120     let ty = expr_ty(bcx, expr);
1121     let v = consts::const_lit(bcx.ccx(), expr, lit);
1122     immediate_rvalue_bcx(bcx, v, ty).to_expr_datumblock()
1123 }
1124
1125 fn trans_unary<'a>(bcx: &'a Block<'a>,
1126                    expr: &ast::Expr,
1127                    op: ast::UnOp,
1128                    sub_expr: &ast::Expr)
1129                    -> DatumBlock<'a, Expr> {
1130     let ccx = bcx.ccx();
1131     let mut bcx = bcx;
1132     let _icx = push_ctxt("trans_unary_datum");
1133
1134     let method_call = MethodCall::expr(expr.id);
1135
1136     // The only overloaded operator that is translated to a datum
1137     // is an overloaded deref, since it is always yields a `&T`.
1138     // Otherwise, we should be in the RvalueDpsExpr path.
1139     assert!(
1140         op == ast::UnDeref ||
1141         !ccx.tcx.method_map.borrow().contains_key(&method_call));
1142
1143     let un_ty = expr_ty(bcx, expr);
1144
1145     match op {
1146         ast::UnNot => {
1147             let datum = unpack_datum!(bcx, trans(bcx, sub_expr));
1148             let llresult = if ty::type_is_bool(un_ty) {
1149                 let val = datum.to_llscalarish(bcx);
1150                 Xor(bcx, val, C_bool(ccx, true))
1151             } else {
1152                 // Note: `Not` is bitwise, not suitable for logical not.
1153                 Not(bcx, datum.to_llscalarish(bcx))
1154             };
1155             immediate_rvalue_bcx(bcx, llresult, un_ty).to_expr_datumblock()
1156         }
1157         ast::UnNeg => {
1158             let datum = unpack_datum!(bcx, trans(bcx, sub_expr));
1159             let val = datum.to_llscalarish(bcx);
1160             let llneg = {
1161                 if ty::type_is_fp(un_ty) {
1162                     FNeg(bcx, val)
1163                 } else {
1164                     Neg(bcx, val)
1165                 }
1166             };
1167             immediate_rvalue_bcx(bcx, llneg, un_ty).to_expr_datumblock()
1168         }
1169         ast::UnBox => {
1170             trans_managed_expr(bcx, un_ty, sub_expr, expr_ty(bcx, sub_expr))
1171         }
1172         ast::UnUniq => {
1173             trans_uniq_expr(bcx, un_ty, sub_expr, expr_ty(bcx, sub_expr))
1174         }
1175         ast::UnDeref => {
1176             let datum = unpack_datum!(bcx, trans(bcx, sub_expr));
1177             deref_once(bcx, expr, datum, method_call)
1178         }
1179     }
1180 }
1181
1182 fn trans_uniq_expr<'a>(bcx: &'a Block<'a>,
1183                        box_ty: ty::t,
1184                        contents: &ast::Expr,
1185                        contents_ty: ty::t)
1186                         -> DatumBlock<'a, Expr> {
1187     let _icx = push_ctxt("trans_uniq_expr");
1188     let fcx = bcx.fcx;
1189     let llty = type_of::type_of(bcx.ccx(), contents_ty);
1190     let size = llsize_of(bcx.ccx(), llty);
1191     let align = C_uint(bcx.ccx(), llalign_of_min(bcx.ccx(), llty) as uint);
1192     // We need to a make a pointer type because box_ty is ty_bot
1193     // if content_ty is, e.g. box fail!().
1194     let real_box_ty = ty::mk_uniq(bcx.tcx(), contents_ty);
1195     let Result { bcx, val } = malloc_raw_dyn(bcx, real_box_ty, size, align);
1196     // Unique boxes do not allocate for zero-size types. The standard library
1197     // may assume that `free` is never called on the pointer returned for
1198     // `Box<ZeroSizeType>`.
1199     let bcx = if llsize_of_alloc(bcx.ccx(), llty) == 0 {
1200         trans_into(bcx, contents, SaveIn(val))
1201     } else {
1202         let custom_cleanup_scope = fcx.push_custom_cleanup_scope();
1203         fcx.schedule_free_value(cleanup::CustomScope(custom_cleanup_scope),
1204                                 val, cleanup::HeapExchange, contents_ty);
1205         let bcx = trans_into(bcx, contents, SaveIn(val));
1206         fcx.pop_custom_cleanup_scope(custom_cleanup_scope);
1207         bcx
1208     };
1209     immediate_rvalue_bcx(bcx, val, box_ty).to_expr_datumblock()
1210 }
1211
1212 fn trans_managed_expr<'a>(bcx: &'a Block<'a>,
1213                           box_ty: ty::t,
1214                           contents: &ast::Expr,
1215                           contents_ty: ty::t)
1216                           -> DatumBlock<'a, Expr> {
1217     let _icx = push_ctxt("trans_managed_expr");
1218     let fcx = bcx.fcx;
1219     let ty = type_of::type_of(bcx.ccx(), contents_ty);
1220     let Result {bcx, val: bx} = malloc_raw_dyn_managed(bcx, contents_ty, MallocFnLangItem,
1221                                                         llsize_of(bcx.ccx(), ty));
1222     let body = GEPi(bcx, bx, [0u, abi::box_field_body]);
1223
1224     let custom_cleanup_scope = fcx.push_custom_cleanup_scope();
1225     fcx.schedule_free_value(cleanup::CustomScope(custom_cleanup_scope),
1226                             bx, cleanup::HeapManaged, contents_ty);
1227     let bcx = trans_into(bcx, contents, SaveIn(body));
1228     fcx.pop_custom_cleanup_scope(custom_cleanup_scope);
1229     immediate_rvalue_bcx(bcx, bx, box_ty).to_expr_datumblock()
1230 }
1231
1232 fn trans_addr_of<'a>(bcx: &'a Block<'a>,
1233                      expr: &ast::Expr,
1234                      subexpr: &ast::Expr)
1235                      -> DatumBlock<'a, Expr> {
1236     let _icx = push_ctxt("trans_addr_of");
1237     let mut bcx = bcx;
1238     let sub_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, subexpr, "addr_of"));
1239     let ty = expr_ty(bcx, expr);
1240     return immediate_rvalue_bcx(bcx, sub_datum.val, ty).to_expr_datumblock();
1241 }
1242
1243 // Important to get types for both lhs and rhs, because one might be _|_
1244 // and the other not.
1245 fn trans_eager_binop<'a>(
1246                      bcx: &'a Block<'a>,
1247                      binop_expr: &ast::Expr,
1248                      binop_ty: ty::t,
1249                      op: ast::BinOp,
1250                      lhs_t: ty::t,
1251                      lhs: ValueRef,
1252                      rhs_t: ty::t,
1253                      rhs: ValueRef)
1254                      -> DatumBlock<'a, Expr> {
1255     let _icx = push_ctxt("trans_eager_binop");
1256
1257     let tcx = bcx.tcx();
1258     let is_simd = ty::type_is_simd(tcx, lhs_t);
1259     let intype = {
1260         if ty::type_is_bot(lhs_t) { rhs_t }
1261         else if is_simd { ty::simd_type(tcx, lhs_t) }
1262         else { lhs_t }
1263     };
1264     let is_float = ty::type_is_fp(intype);
1265     let is_signed = ty::type_is_signed(intype);
1266
1267     let rhs = base::cast_shift_expr_rhs(bcx, op, lhs, rhs);
1268
1269     let mut bcx = bcx;
1270     let val = match op {
1271       ast::BiAdd => {
1272         if is_float { FAdd(bcx, lhs, rhs) }
1273         else { Add(bcx, lhs, rhs) }
1274       }
1275       ast::BiSub => {
1276         if is_float { FSub(bcx, lhs, rhs) }
1277         else { Sub(bcx, lhs, rhs) }
1278       }
1279       ast::BiMul => {
1280         if is_float { FMul(bcx, lhs, rhs) }
1281         else { Mul(bcx, lhs, rhs) }
1282       }
1283       ast::BiDiv => {
1284         if is_float {
1285             FDiv(bcx, lhs, rhs)
1286         } else {
1287             // Only zero-check integers; fp /0 is NaN
1288             bcx = base::fail_if_zero_or_overflows(bcx, binop_expr.span,
1289                                                   op, lhs, rhs, rhs_t);
1290             if is_signed {
1291                 SDiv(bcx, lhs, rhs)
1292             } else {
1293                 UDiv(bcx, lhs, rhs)
1294             }
1295         }
1296       }
1297       ast::BiRem => {
1298         if is_float {
1299             FRem(bcx, lhs, rhs)
1300         } else {
1301             // Only zero-check integers; fp %0 is NaN
1302             bcx = base::fail_if_zero_or_overflows(bcx, binop_expr.span,
1303                                                   op, lhs, rhs, rhs_t);
1304             if is_signed {
1305                 SRem(bcx, lhs, rhs)
1306             } else {
1307                 URem(bcx, lhs, rhs)
1308             }
1309         }
1310       }
1311       ast::BiBitOr => Or(bcx, lhs, rhs),
1312       ast::BiBitAnd => And(bcx, lhs, rhs),
1313       ast::BiBitXor => Xor(bcx, lhs, rhs),
1314       ast::BiShl => Shl(bcx, lhs, rhs),
1315       ast::BiShr => {
1316         if is_signed {
1317             AShr(bcx, lhs, rhs)
1318         } else { LShr(bcx, lhs, rhs) }
1319       }
1320       ast::BiEq | ast::BiNe | ast::BiLt | ast::BiGe | ast::BiLe | ast::BiGt => {
1321         if ty::type_is_bot(rhs_t) {
1322             C_bool(bcx.ccx(), false)
1323         } else if ty::type_is_scalar(rhs_t) {
1324             unpack_result!(bcx, base::compare_scalar_types(bcx, lhs, rhs, rhs_t, op))
1325         } else if is_simd {
1326             base::compare_simd_types(bcx, lhs, rhs, intype, ty::simd_size(tcx, lhs_t), op)
1327         } else {
1328             bcx.tcx().sess.span_bug(binop_expr.span, "comparison operator unsupported for type")
1329         }
1330       }
1331       _ => {
1332         bcx.tcx().sess.span_bug(binop_expr.span, "unexpected binop");
1333       }
1334     };
1335
1336     immediate_rvalue_bcx(bcx, val, binop_ty).to_expr_datumblock()
1337 }
1338
1339 // refinement types would obviate the need for this
1340 enum lazy_binop_ty {
1341     lazy_and,
1342     lazy_or,
1343 }
1344
1345 fn trans_lazy_binop<'a>(
1346                     bcx: &'a Block<'a>,
1347                     binop_expr: &ast::Expr,
1348                     op: lazy_binop_ty,
1349                     a: &ast::Expr,
1350                     b: &ast::Expr)
1351                     -> DatumBlock<'a, Expr> {
1352     let _icx = push_ctxt("trans_lazy_binop");
1353     let binop_ty = expr_ty(bcx, binop_expr);
1354     let fcx = bcx.fcx;
1355
1356     let DatumBlock {bcx: past_lhs, datum: lhs} = trans(bcx, a);
1357     let lhs = lhs.to_llscalarish(past_lhs);
1358
1359     if past_lhs.unreachable.get() {
1360         return immediate_rvalue_bcx(past_lhs, lhs, binop_ty).to_expr_datumblock();
1361     }
1362
1363     let join = fcx.new_id_block("join", binop_expr.id);
1364     let before_rhs = fcx.new_id_block("before_rhs", b.id);
1365
1366     match op {
1367       lazy_and => CondBr(past_lhs, lhs, before_rhs.llbb, join.llbb),
1368       lazy_or => CondBr(past_lhs, lhs, join.llbb, before_rhs.llbb)
1369     }
1370
1371     let DatumBlock {bcx: past_rhs, datum: rhs} = trans(before_rhs, b);
1372     let rhs = rhs.to_llscalarish(past_rhs);
1373
1374     if past_rhs.unreachable.get() {
1375         return immediate_rvalue_bcx(join, lhs, binop_ty).to_expr_datumblock();
1376     }
1377
1378     Br(past_rhs, join.llbb);
1379     let phi = Phi(join, Type::bool(bcx.ccx()), [lhs, rhs],
1380                   [past_lhs.llbb, past_rhs.llbb]);
1381
1382     return immediate_rvalue_bcx(join, phi, binop_ty).to_expr_datumblock();
1383 }
1384
1385 fn trans_binary<'a>(bcx: &'a Block<'a>,
1386                     expr: &ast::Expr,
1387                     op: ast::BinOp,
1388                     lhs: &ast::Expr,
1389                     rhs: &ast::Expr)
1390                     -> DatumBlock<'a, Expr> {
1391     let _icx = push_ctxt("trans_binary");
1392     let ccx = bcx.ccx();
1393
1394     // if overloaded, would be RvalueDpsExpr
1395     assert!(!ccx.tcx.method_map.borrow().contains_key(&MethodCall::expr(expr.id)));
1396
1397     match op {
1398         ast::BiAnd => {
1399             trans_lazy_binop(bcx, expr, lazy_and, lhs, rhs)
1400         }
1401         ast::BiOr => {
1402             trans_lazy_binop(bcx, expr, lazy_or, lhs, rhs)
1403         }
1404         _ => {
1405             let mut bcx = bcx;
1406             let lhs_datum = unpack_datum!(bcx, trans(bcx, lhs));
1407             let rhs_datum = unpack_datum!(bcx, trans(bcx, rhs));
1408             let binop_ty = expr_ty(bcx, expr);
1409
1410             debug!("trans_binary (expr {}): lhs_datum={}",
1411                    expr.id,
1412                    lhs_datum.to_str(ccx));
1413             let lhs_ty = lhs_datum.ty;
1414             let lhs = lhs_datum.to_llscalarish(bcx);
1415
1416             debug!("trans_binary (expr {}): rhs_datum={}",
1417                    expr.id,
1418                    rhs_datum.to_str(ccx));
1419             let rhs_ty = rhs_datum.ty;
1420             let rhs = rhs_datum.to_llscalarish(bcx);
1421             trans_eager_binop(bcx, expr, binop_ty, op,
1422                               lhs_ty, lhs, rhs_ty, rhs)
1423         }
1424     }
1425 }
1426
1427 fn trans_overloaded_op<'a, 'b>(
1428                        bcx: &'a Block<'a>,
1429                        expr: &ast::Expr,
1430                        method_call: MethodCall,
1431                        lhs: Datum<Expr>,
1432                        rhs: Option<(Datum<Expr>, ast::NodeId)>,
1433                        dest: Option<Dest>)
1434                        -> Result<'a> {
1435     let method_ty = bcx.tcx().method_map.borrow().get(&method_call).ty;
1436     callee::trans_call_inner(bcx,
1437                              Some(expr_info(expr)),
1438                              monomorphize_type(bcx, method_ty),
1439                              |bcx, arg_cleanup_scope| {
1440                                 meth::trans_method_callee(bcx,
1441                                                           method_call,
1442                                                           None,
1443                                                           arg_cleanup_scope)
1444                              },
1445                              callee::ArgOverloadedOp(lhs, rhs),
1446                              dest)
1447 }
1448
1449 fn trans_overloaded_call<'a>(
1450                          mut bcx: &'a Block<'a>,
1451                          expr: &ast::Expr,
1452                          callee: Datum<Expr>,
1453                          args: &[Gc<ast::Expr>],
1454                          dest: Option<Dest>)
1455                          -> &'a Block<'a> {
1456     // Evaluate and tuple the arguments.
1457     let tuple_type = ty::mk_tup(bcx.tcx(),
1458                                 args.iter()
1459                                     .map(|e| ty::expr_ty_adjusted(bcx.tcx(), &**e))
1460                                     .collect());
1461     let repr = adt::represent_type(bcx.ccx(), tuple_type);
1462     let numbered_fields: Vec<(uint, Gc<ast::Expr>)> =
1463         args.iter().enumerate().map(|(i, arg)| (i, *arg)).collect();
1464     let argument_scope = bcx.fcx.push_custom_cleanup_scope();
1465     let tuple_datum =
1466         unpack_datum!(bcx,
1467                       lvalue_scratch_datum(bcx,
1468                                            tuple_type,
1469                                            "tupled_arguments",
1470                                            false,
1471                                            cleanup::CustomScope(
1472                                                argument_scope),
1473                                            (),
1474                                            |(), bcx, addr| {
1475             trans_adt(bcx,
1476                       &*repr,
1477                       0,
1478                       numbered_fields.as_slice(),
1479                       None,
1480                       SaveIn(addr))
1481         }));
1482
1483     let method_call = MethodCall::expr(expr.id);
1484     let method_type = bcx.tcx()
1485                          .method_map
1486                          .borrow()
1487                          .get(&method_call)
1488                          .ty;
1489     let callee_rvalue = unpack_datum!(bcx,
1490                                       callee.to_rvalue_datum(bcx, "callee"));
1491     let tuple_datum = tuple_datum.to_expr_datum();
1492     let tuple_rvalue = unpack_datum!(bcx,
1493                                      tuple_datum.to_rvalue_datum(bcx,
1494                                                                  "tuple"));
1495     let argument_values = [
1496         callee_rvalue.add_clean(bcx.fcx,
1497                                 cleanup::CustomScope(argument_scope)),
1498         tuple_rvalue.add_clean(bcx.fcx, cleanup::CustomScope(argument_scope))
1499     ];
1500     unpack_result!(bcx,
1501                    callee::trans_call_inner(bcx,
1502                                             Some(expr_info(expr)),
1503                                             monomorphize_type(bcx,
1504                                                               method_type),
1505                                             |bcx, arg_cleanup_scope| {
1506                                                 meth::trans_method_callee(
1507                                                     bcx,
1508                                                     method_call,
1509                                                     None,
1510                                                     arg_cleanup_scope)
1511                                             },
1512                                             callee::ArgVals(argument_values),
1513                                             dest));
1514
1515     bcx.fcx.pop_custom_cleanup_scope(argument_scope);
1516     bcx
1517 }
1518
1519 fn int_cast(bcx: &Block,
1520             lldsttype: Type,
1521             llsrctype: Type,
1522             llsrc: ValueRef,
1523             signed: bool)
1524             -> ValueRef {
1525     let _icx = push_ctxt("int_cast");
1526     unsafe {
1527         let srcsz = llvm::LLVMGetIntTypeWidth(llsrctype.to_ref());
1528         let dstsz = llvm::LLVMGetIntTypeWidth(lldsttype.to_ref());
1529         return if dstsz == srcsz {
1530             BitCast(bcx, llsrc, lldsttype)
1531         } else if srcsz > dstsz {
1532             TruncOrBitCast(bcx, llsrc, lldsttype)
1533         } else if signed {
1534             SExtOrBitCast(bcx, llsrc, lldsttype)
1535         } else {
1536             ZExtOrBitCast(bcx, llsrc, lldsttype)
1537         };
1538     }
1539 }
1540
1541 fn float_cast(bcx: &Block,
1542               lldsttype: Type,
1543               llsrctype: Type,
1544               llsrc: ValueRef)
1545               -> ValueRef {
1546     let _icx = push_ctxt("float_cast");
1547     let srcsz = llsrctype.float_width();
1548     let dstsz = lldsttype.float_width();
1549     return if dstsz > srcsz {
1550         FPExt(bcx, llsrc, lldsttype)
1551     } else if srcsz > dstsz {
1552         FPTrunc(bcx, llsrc, lldsttype)
1553     } else { llsrc };
1554 }
1555
1556 #[deriving(PartialEq)]
1557 pub enum cast_kind {
1558     cast_pointer,
1559     cast_integral,
1560     cast_float,
1561     cast_enum,
1562     cast_other,
1563 }
1564
1565 pub fn cast_type_kind(t: ty::t) -> cast_kind {
1566     match ty::get(t).sty {
1567         ty::ty_char        => cast_integral,
1568         ty::ty_float(..)   => cast_float,
1569         ty::ty_ptr(..)     => cast_pointer,
1570         ty::ty_rptr(_, mt) => match ty::get(mt.ty).sty{
1571             ty::ty_vec(_, None) | ty::ty_str | ty::ty_trait(..) => cast_other,
1572             _ => cast_pointer,
1573         },
1574         ty::ty_bare_fn(..) => cast_pointer,
1575         ty::ty_int(..)     => cast_integral,
1576         ty::ty_uint(..)    => cast_integral,
1577         ty::ty_bool        => cast_integral,
1578         ty::ty_enum(..)    => cast_enum,
1579         _                  => cast_other
1580     }
1581 }
1582
1583 fn trans_imm_cast<'a>(bcx: &'a Block<'a>,
1584                       expr: &ast::Expr,
1585                       id: ast::NodeId)
1586                       -> DatumBlock<'a, Expr> {
1587     let _icx = push_ctxt("trans_cast");
1588     let mut bcx = bcx;
1589     let ccx = bcx.ccx();
1590
1591     let t_in = expr_ty(bcx, expr);
1592     let t_out = node_id_type(bcx, id);
1593     let k_in = cast_type_kind(t_in);
1594     let k_out = cast_type_kind(t_out);
1595     let s_in = k_in == cast_integral && ty::type_is_signed(t_in);
1596     let ll_t_in = type_of::type_of(ccx, t_in);
1597     let ll_t_out = type_of::type_of(ccx, t_out);
1598
1599     // Convert the value to be cast into a ValueRef, either by-ref or
1600     // by-value as appropriate given its type:
1601     let datum = unpack_datum!(bcx, trans(bcx, expr));
1602     let newval = match (k_in, k_out) {
1603         (cast_integral, cast_integral) => {
1604             let llexpr = datum.to_llscalarish(bcx);
1605             int_cast(bcx, ll_t_out, ll_t_in, llexpr, s_in)
1606         }
1607         (cast_float, cast_float) => {
1608             let llexpr = datum.to_llscalarish(bcx);
1609             float_cast(bcx, ll_t_out, ll_t_in, llexpr)
1610         }
1611         (cast_integral, cast_float) => {
1612             let llexpr = datum.to_llscalarish(bcx);
1613             if s_in {
1614                 SIToFP(bcx, llexpr, ll_t_out)
1615             } else { UIToFP(bcx, llexpr, ll_t_out) }
1616         }
1617         (cast_float, cast_integral) => {
1618             let llexpr = datum.to_llscalarish(bcx);
1619             if ty::type_is_signed(t_out) {
1620                 FPToSI(bcx, llexpr, ll_t_out)
1621             } else { FPToUI(bcx, llexpr, ll_t_out) }
1622         }
1623         (cast_integral, cast_pointer) => {
1624             let llexpr = datum.to_llscalarish(bcx);
1625             IntToPtr(bcx, llexpr, ll_t_out)
1626         }
1627         (cast_pointer, cast_integral) => {
1628             let llexpr = datum.to_llscalarish(bcx);
1629             PtrToInt(bcx, llexpr, ll_t_out)
1630         }
1631         (cast_pointer, cast_pointer) => {
1632             let llexpr = datum.to_llscalarish(bcx);
1633             PointerCast(bcx, llexpr, ll_t_out)
1634         }
1635         (cast_enum, cast_integral) |
1636         (cast_enum, cast_float) => {
1637             let mut bcx = bcx;
1638             let repr = adt::represent_type(ccx, t_in);
1639             let datum = unpack_datum!(
1640                 bcx, datum.to_lvalue_datum(bcx, "trans_imm_cast", expr.id));
1641             let llexpr_ptr = datum.to_llref();
1642             let lldiscrim_a =
1643                 adt::trans_get_discr(bcx, &*repr, llexpr_ptr, Some(Type::i64(ccx)));
1644             match k_out {
1645                 cast_integral => int_cast(bcx, ll_t_out,
1646                                           val_ty(lldiscrim_a),
1647                                           lldiscrim_a, true),
1648                 cast_float => SIToFP(bcx, lldiscrim_a, ll_t_out),
1649                 _ => {
1650                     ccx.sess().bug(format!("translating unsupported cast: \
1651                                             {} ({:?}) -> {} ({:?})",
1652                                             t_in.repr(bcx.tcx()),
1653                                             k_in,
1654                                             t_out.repr(bcx.tcx()),
1655                                             k_out).as_slice())
1656                 }
1657             }
1658         }
1659         _ => ccx.sess().bug(format!("translating unsupported cast: \
1660                                     {} ({:?}) -> {} ({:?})",
1661                                     t_in.repr(bcx.tcx()),
1662                                     k_in,
1663                                     t_out.repr(bcx.tcx()),
1664                                     k_out).as_slice())
1665     };
1666     return immediate_rvalue_bcx(bcx, newval, t_out).to_expr_datumblock();
1667 }
1668
1669 fn trans_assign_op<'a>(
1670                    bcx: &'a Block<'a>,
1671                    expr: &ast::Expr,
1672                    op: ast::BinOp,
1673                    dst: &ast::Expr,
1674                    src: Gc<ast::Expr>)
1675                    -> &'a Block<'a> {
1676     let _icx = push_ctxt("trans_assign_op");
1677     let mut bcx = bcx;
1678
1679     debug!("trans_assign_op(expr={})", bcx.expr_to_str(expr));
1680
1681     // User-defined operator methods cannot be used with `+=` etc right now
1682     assert!(!bcx.tcx().method_map.borrow().contains_key(&MethodCall::expr(expr.id)));
1683
1684     // Evaluate LHS (destination), which should be an lvalue
1685     let dst_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, dst, "assign_op"));
1686     assert!(!ty::type_needs_drop(bcx.tcx(), dst_datum.ty));
1687     let dst_ty = dst_datum.ty;
1688     let dst = Load(bcx, dst_datum.val);
1689
1690     // Evaluate RHS
1691     let rhs_datum = unpack_datum!(bcx, trans(bcx, &*src));
1692     let rhs_ty = rhs_datum.ty;
1693     let rhs = rhs_datum.to_llscalarish(bcx);
1694
1695     // Perform computation and store the result
1696     let result_datum = unpack_datum!(
1697         bcx, trans_eager_binop(bcx, expr, dst_datum.ty, op,
1698                                dst_ty, dst, rhs_ty, rhs));
1699     return result_datum.store_to(bcx, dst_datum.val);
1700 }
1701
1702 fn auto_ref<'a>(bcx: &'a Block<'a>,
1703                 datum: Datum<Expr>,
1704                 expr: &ast::Expr)
1705                 -> DatumBlock<'a, Expr> {
1706     let mut bcx = bcx;
1707
1708     // Ensure cleanup of `datum` if not already scheduled and obtain
1709     // a "by ref" pointer.
1710     let lv_datum = unpack_datum!(bcx, datum.to_lvalue_datum(bcx, "autoref", expr.id));
1711
1712     // Compute final type. Note that we are loose with the region and
1713     // mutability, since those things don't matter in trans.
1714     let referent_ty = lv_datum.ty;
1715     let ptr_ty = ty::mk_imm_rptr(bcx.tcx(), ty::ReStatic, referent_ty);
1716
1717     // Get the pointer.
1718     let llref = lv_datum.to_llref();
1719
1720     // Construct the resulting datum, using what was the "by ref"
1721     // ValueRef of type `referent_ty` to be the "by value" ValueRef
1722     // of type `&referent_ty`.
1723     DatumBlock::new(bcx, Datum::new(llref, ptr_ty, RvalueExpr(Rvalue::new(ByValue))))
1724 }
1725
1726 fn deref_multiple<'a>(bcx: &'a Block<'a>,
1727                       expr: &ast::Expr,
1728                       datum: Datum<Expr>,
1729                       times: uint)
1730                       -> DatumBlock<'a, Expr> {
1731     let mut bcx = bcx;
1732     let mut datum = datum;
1733     for i in range(0, times) {
1734         let method_call = MethodCall::autoderef(expr.id, i);
1735         datum = unpack_datum!(bcx, deref_once(bcx, expr, datum, method_call));
1736     }
1737     DatumBlock { bcx: bcx, datum: datum }
1738 }
1739
1740 fn deref_once<'a>(bcx: &'a Block<'a>,
1741                   expr: &ast::Expr,
1742                   datum: Datum<Expr>,
1743                   method_call: MethodCall)
1744                   -> DatumBlock<'a, Expr> {
1745     let ccx = bcx.ccx();
1746
1747     debug!("deref_once(expr={}, datum={}, method_call={})",
1748            expr.repr(bcx.tcx()),
1749            datum.to_str(ccx),
1750            method_call);
1751
1752     let mut bcx = bcx;
1753
1754     // Check for overloaded deref.
1755     let method_ty = ccx.tcx.method_map.borrow()
1756                        .find(&method_call).map(|method| method.ty);
1757     let datum = match method_ty {
1758         Some(method_ty) => {
1759             // Overloaded. Evaluate `trans_overloaded_op`, which will
1760             // invoke the user's deref() method, which basically
1761             // converts from the `Shaht<T>` pointer that we have into
1762             // a `&T` pointer.  We can then proceed down the normal
1763             // path (below) to dereference that `&T`.
1764             let datum = match method_call.adjustment {
1765                 // Always perform an AutoPtr when applying an overloaded auto-deref
1766                 typeck::AutoDeref(_) => unpack_datum!(bcx, auto_ref(bcx, datum, expr)),
1767                 _ => datum
1768             };
1769             let val = unpack_result!(bcx, trans_overloaded_op(bcx, expr, method_call,
1770                                                               datum, None, None));
1771             let ref_ty = ty::ty_fn_ret(monomorphize_type(bcx, method_ty));
1772             Datum::new(val, ref_ty, RvalueExpr(Rvalue::new(ByValue)))
1773         }
1774         None => {
1775             // Not overloaded. We already have a pointer we know how to deref.
1776             datum
1777         }
1778     };
1779
1780     let r = match ty::get(datum.ty).sty {
1781         ty::ty_uniq(content_ty) => {
1782             match ty::get(content_ty).sty {
1783                 ty::ty_vec(_, None) | ty::ty_str | ty::ty_trait(..)
1784                     => bcx.tcx().sess.span_bug(expr.span, "unexpected unsized box"),
1785                 _ => deref_owned_pointer(bcx, expr, datum, content_ty),
1786             }
1787         }
1788
1789         ty::ty_box(content_ty) => {
1790             let datum = unpack_datum!(
1791                 bcx, datum.to_lvalue_datum(bcx, "deref", expr.id));
1792             let llptrref = datum.to_llref();
1793             let llptr = Load(bcx, llptrref);
1794             let llbody = GEPi(bcx, llptr, [0u, abi::box_field_body]);
1795             DatumBlock::new(bcx, Datum::new(llbody, content_ty, LvalueExpr))
1796         }
1797
1798         ty::ty_ptr(ty::mt { ty: content_ty, .. }) |
1799         ty::ty_rptr(_, ty::mt { ty: content_ty, .. }) => {
1800             match ty::get(content_ty).sty {
1801                 ty::ty_vec(_, None) | ty::ty_str | ty::ty_trait(..)
1802                     => bcx.tcx().sess.span_bug(expr.span, "unexpected unsized reference"),
1803                 _ => {
1804                     assert!(!ty::type_needs_drop(bcx.tcx(), datum.ty));
1805
1806                     let ptr = datum.to_llscalarish(bcx);
1807
1808                     // Always generate an lvalue datum, even if datum.mode is
1809                     // an rvalue.  This is because datum.mode is only an
1810                     // rvalue for non-owning pointers like &T or *T, in which
1811                     // case cleanup *is* scheduled elsewhere, by the true
1812                     // owner (or, in the case of *T, by the user).
1813                     DatumBlock::new(bcx, Datum::new(ptr, content_ty, LvalueExpr))
1814                 }
1815             }
1816         }
1817
1818         _ => {
1819             bcx.tcx().sess.span_bug(
1820                 expr.span,
1821                 format!("deref invoked on expr of illegal type {}",
1822                         datum.ty.repr(bcx.tcx())).as_slice());
1823         }
1824     };
1825
1826     debug!("deref_once(expr={}, method_call={}, result={})",
1827            expr.id, method_call, r.datum.to_str(ccx));
1828
1829     return r;
1830
1831     fn deref_owned_pointer<'a>(bcx: &'a Block<'a>,
1832                                expr: &ast::Expr,
1833                                datum: Datum<Expr>,
1834                                content_ty: ty::t)
1835                                -> DatumBlock<'a, Expr> {
1836         /*!
1837          * We microoptimize derefs of owned pointers a bit here.
1838          * Basically, the idea is to make the deref of an rvalue
1839          * result in an rvalue. This helps to avoid intermediate stack
1840          * slots in the resulting LLVM. The idea here is that, if the
1841          * `Box<T>` pointer is an rvalue, then we can schedule a *shallow*
1842          * free of the `Box<T>` pointer, and then return a ByRef rvalue
1843          * into the pointer. Because the free is shallow, it is legit
1844          * to return an rvalue, because we know that the contents are
1845          * not yet scheduled to be freed. The language rules ensure that the
1846          * contents will be used (or moved) before the free occurs.
1847          */
1848
1849         match datum.kind {
1850             RvalueExpr(Rvalue { mode: ByRef }) => {
1851                 let scope = cleanup::temporary_scope(bcx.tcx(), expr.id);
1852                 let ptr = Load(bcx, datum.val);
1853                 if !type_is_zero_size(bcx.ccx(), content_ty) {
1854                     bcx.fcx.schedule_free_value(scope, ptr, cleanup::HeapExchange, content_ty);
1855                 }
1856             }
1857             RvalueExpr(Rvalue { mode: ByValue }) => {
1858                 let scope = cleanup::temporary_scope(bcx.tcx(), expr.id);
1859                 if !type_is_zero_size(bcx.ccx(), content_ty) {
1860                     bcx.fcx.schedule_free_value(scope, datum.val, cleanup::HeapExchange,
1861                                                 content_ty);
1862                 }
1863             }
1864             LvalueExpr => { }
1865         }
1866
1867         // If we had an rvalue in, we produce an rvalue out.
1868         let (llptr, kind) = match datum.kind {
1869             LvalueExpr => {
1870                 (Load(bcx, datum.val), LvalueExpr)
1871             }
1872             RvalueExpr(Rvalue { mode: ByRef }) => {
1873                 (Load(bcx, datum.val), RvalueExpr(Rvalue::new(ByRef)))
1874             }
1875             RvalueExpr(Rvalue { mode: ByValue }) => {
1876                 (datum.val, RvalueExpr(Rvalue::new(ByRef)))
1877             }
1878         };
1879
1880         let datum = Datum { ty: content_ty, val: llptr, kind: kind };
1881         DatumBlock { bcx: bcx, datum: datum }
1882     }
1883 }