src/librustc/middle/trans/expr.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 /*!
  12
  13 # Translation of expressions.
  14
  15 ## Recommended entry point
  16
  17 If you wish to translate an expression, the preferred way to do
  18 so is to use:
  19
  20     expr::trans_into(block, expr, Dest) -> block
  21
  22 This will generate code that evaluates `expr`, storing the result into
  23 `Dest`, which must either be the special flag ignore (throw the result
  24 away) or be a pointer to memory of the same type/size as the
  25 expression.  It returns the resulting basic block.  This form will
  26 handle all automatic adjustments for you. The value will be moved if
  27 its type is linear and copied otherwise.
  28
  29 ## Translation to a datum
  30
  31 In some cases, `trans_into()` is too narrow of an interface.
  32 Generally this occurs either when you know that the result value is
  33 going to be a scalar, or when you need to evaluate the expression into
  34 some memory location so you can go and inspect it (e.g., assignments,
  35 `match` expressions, the `&` operator).
  36
  37 In such cases, you want the following function:
  38
  39     trans_to_datum(block, expr) -> DatumBlock
  40
  41 This function generates code to evaluate the expression and return a
  42 `Datum` describing where the result is to be found.  This function
  43 tries to return its result in the most efficient way possible, without
  44 introducing extra copies or sacrificing information.  Therefore, for
  45 lvalue expressions, you always get a by-ref `Datum` in return that
  46 points at the memory for this lvalue.  For rvalue expressions, we will
  47 return a by-value `Datum` whenever possible, but it is often necessary
  48 to allocate a stack slot, store the result of the rvalue in there, and
  49 then return a pointer to the slot (see the discussion later on about
  50 the different kinds of rvalues).
  51
  52 NB: The `trans_to_datum()` function does perform adjustments, but
  53 since it returns a pointer to the value "in place" it does not handle
  54 moves.  If you wish to copy/move the value returned into a new
  55 location, you should use the Datum method `store_to()` (move or copy
  56 depending on type). You can also use `move_to()` (force move) or
  57 `copy_to()` (force copy) for special situations.
  58
  59 ## Translating local variables
  60
  61 `trans_local_var()` can be used to trans a ref to a local variable
  62 that is not an expression.  This is needed for captures.
  63
  64 ## Ownership and cleanups
  65
  66 The current system for cleanups associates required cleanups with
  67 block contexts.  Block contexts are structured into a tree that
  68 resembles the code itself.  Not every block context has cleanups
  69 associated with it, only those blocks that have a kind of
  70 `block_scope`.  See `common::block_kind` for more details.
  71
  72 If you invoke `trans_into()`, no cleanup is scheduled for you.  The
  73 value is written into the given destination and is assumed to be owned
  74 by that destination.
  75
  76 When you invoke `trans_to_datum()` on an rvalue, the resulting
  77 datum/value will have an appropriate cleanup scheduled for the
  78 innermost cleanup scope.  If you later use `move_to()` or
  79 `drop_val()`, this cleanup will be canceled.
  80
  81 During the evaluation of an expression, temporary cleanups are created
  82 and later canceled.  These represent intermediate or partial results
  83 which must be cleaned up in the event of task failure.
  84
  85 ## Implementation details
  86
  87 We divide expressions into three categories, based on how they are most
  88 naturally implemented:
  89
  90 1. Lvalues
  91 2. Datum rvalues
  92 3. DPS rvalues
  93 4. Statement rvalues
  94
  95 Lvalues always refer to user-assignable memory locations.
  96 Translating those always results in a by-ref datum; this introduces
  97 no inefficiencies into the generated code, because all lvalues are
  98 naturally addressable.
  99
 100 Datum rvalues are rvalues that always generate datums as a result.
 101 These are generally scalar results, such as `a+b` where `a` and `b`
 102 are integers.
 103
 104 DPS rvalues are rvalues that, when translated, must be given a
 105 memory location to write into (or the Ignore flag).  These are
 106 generally expressions that produce structural results that are
 107 larger than one word (e.g., a struct literal), but also expressions
 108 (like `if`) that involve control flow (otherwise we'd have to
 109 generate phi nodes).
 110
 111 Finally, statement rvalues are rvalues that always produce a nil
 112 return type, such as `while` loops or assignments (`a = b`).
 113
 114 */
 115
 116
 117 use back::abi;
 118 use lib::llvm::{ValueRef, llvm, SetLinkage, ExternalLinkage};
 119 use lib;
 120 use metadata::csearch;
 121 use middle::trans::_match;
 122 use middle::trans::adt;
 123 use middle::trans::asm;
 124 use middle::trans::base::*;
 125 use middle::trans::base;
 126 use middle::trans::build::*;
 127 use middle::trans::callee::DoAutorefArg;
 128 use middle::trans::callee;
 129 use middle::trans::closure;
 130 use middle::trans::common::*;
 131 use middle::trans::consts;
 132 use middle::trans::controlflow;
 133 use middle::trans::datum::*;
 134 use middle::trans::debuginfo;
 135 use middle::trans::machine;
 136 use middle::trans::meth;
 137 use middle::trans::tvec;
 138 use middle::trans::type_of;
 139 use middle::ty::struct_fields;
 140 use middle::ty::{AutoBorrowObj, AutoDerefRef, AutoAddEnv, AutoUnsafe};
 141 use middle::ty::{AutoPtr, AutoBorrowVec, AutoBorrowVecRef, AutoBorrowFn};
 142 use middle::ty;
 143 use util::common::indenter;
 144 use util::ppaux::Repr;
 145 use middle::trans::machine::llsize_of;
 146
 147 use middle::trans::type_::Type;
 148
 149 use std::hashmap::HashMap;
 150 use std::vec;
 151 use syntax::print::pprust::{expr_to_str};
 152 use syntax::ast;
 153 use syntax::codemap;
 154
 155 // Destinations
 156
 157 // These are passed around by the code generating functions to track the
 158 // destination of a computation's value.
 159
 160 #[deriving(Eq)]
 161 pub enum Dest {
 162     SaveIn(ValueRef),
 163     Ignore,
 164 }
 165
 166 impl Dest {
 167     pub fn to_str(&self, ccx: &CrateContext) -> ~str {
 168         match *self {
 169             SaveIn(v) => fmt!("SaveIn(%s)", ccx.tn.val_to_str(v)),
 170             Ignore => ~"Ignore"
 171         }
 172     }
 173 }
 174
 175 fn drop_and_cancel_clean(bcx: @mut Block, dat: Datum) -> @mut Block {
 176     let bcx = dat.drop_val(bcx);
 177     dat.cancel_clean(bcx);
 178     return bcx;
 179 }
 180
 181 pub fn trans_to_datum(bcx: @mut Block, expr: @ast::expr) -> DatumBlock {
 182     debug!("trans_to_datum(expr=%s)", bcx.expr_to_str(expr));
 183
 184     let mut bcx = bcx;
 185     let mut datum = unpack_datum!(bcx, trans_to_datum_unadjusted(bcx, expr));
 186     let adjustment = match bcx.tcx().adjustments.find_copy(&expr.id) {
 187         None => { return DatumBlock {bcx: bcx, datum: datum}; }
 188         Some(adj) => { adj }
 189     };
 190     debug!("unadjusted datum: %s", datum.to_str(bcx.ccx()));
 191     match *adjustment {
 192         AutoAddEnv(*) => {
 193             datum = unpack_datum!(bcx, add_env(bcx, expr, datum));
 194         }
 195         AutoDerefRef(ref adj) => {
 196             if adj.autoderefs > 0 {
 197                 datum =
 198                     unpack_datum!(
 199                         bcx,
 200                         datum.autoderef(bcx, expr.span,
 201                                         expr.id, adj.autoderefs));
 202             }
 203
 204             datum = match adj.autoref {
 205                 None => {
 206                     datum
 207                 }
 208                 Some(AutoUnsafe(*)) | // region + unsafe ptrs have same repr
 209                 Some(AutoPtr(*)) => {
 210                     unpack_datum!(bcx, auto_ref(bcx, datum))
 211                 }
 212                 Some(AutoBorrowVec(*)) => {
 213                     unpack_datum!(bcx, auto_slice(bcx, adj.autoderefs,
 214                                                   expr, datum))
 215                 }
 216                 Some(AutoBorrowVecRef(*)) => {
 217                     unpack_datum!(bcx, auto_slice_and_ref(bcx, adj.autoderefs,
 218                                                           expr, datum))
 219                 }
 220                 Some(AutoBorrowFn(*)) => {
 221                     let adjusted_ty = ty::adjust_ty(bcx.tcx(), expr.span,
 222                                                     datum.ty, Some(adjustment));
 223                     unpack_datum!(bcx, auto_borrow_fn(bcx, adjusted_ty, datum))
 224                 }
 225                 Some(AutoBorrowObj(*)) => {
 226                     unpack_datum!(bcx, auto_borrow_obj(
 227                         bcx, adj.autoderefs, expr, datum))
 228                 }
 229             };
 230         }
 231     }
 232     debug!("after adjustments, datum=%s", datum.to_str(bcx.ccx()));
 233     return DatumBlock {bcx: bcx, datum: datum};
 234
 235     fn auto_ref(bcx: @mut Block, datum: Datum) -> DatumBlock {
 236         DatumBlock {bcx: bcx, datum: datum.to_rptr(bcx)}
 237     }
 238
 239     fn auto_borrow_fn(bcx: @mut Block,
 240                       adjusted_ty: ty::t,
 241                       datum: Datum) -> DatumBlock {
 242         // Currently, all closure types are represented precisely the
 243         // same, so no runtime adjustment is required, but we still
 244         // must patchup the type.
 245         DatumBlock {bcx: bcx,
 246                     datum: Datum {val: datum.val, ty: adjusted_ty,
 247                                   mode: datum.mode}}
 248     }
 249
 250     fn auto_slice(bcx: @mut Block,
 251                   autoderefs: uint,
 252                   expr: &ast::expr,
 253                   datum: Datum) -> DatumBlock {
 254         // This is not the most efficient thing possible; since slices
 255         // are two words it'd be better if this were compiled in
 256         // 'dest' mode, but I can't find a nice way to structure the
 257         // code and keep it DRY that accommodates that use case at the
 258         // moment.
 259
 260         let tcx = bcx.tcx();
 261         let unit_ty = ty::sequence_element_type(tcx, datum.ty);
 262
 263         let (bcx, base, len) =
 264             datum.get_vec_base_and_len(bcx, expr.span, expr.id, autoderefs+1);
 265
 266         // this type may have a different region/mutability than the
 267         // real one, but it will have the same runtime representation
 268         let slice_ty = ty::mk_evec(tcx,
 269                                    ty::mt { ty: unit_ty, mutbl: ast::m_imm },
 270                                    ty::vstore_slice(ty::re_static));
 271
 272         let scratch = scratch_datum(bcx, slice_ty, "__adjust", false);
 273         Store(bcx, base, GEPi(bcx, scratch.val, [0u, abi::slice_elt_base]));
 274         Store(bcx, len, GEPi(bcx, scratch.val, [0u, abi::slice_elt_len]));
 275         DatumBlock {bcx: bcx, datum: scratch}
 276     }
 277
 278     fn add_env(bcx: @mut Block, expr: &ast::expr, datum: Datum) -> DatumBlock {
 279         // This is not the most efficient thing possible; since closures
 280         // are two words it'd be better if this were compiled in
 281         // 'dest' mode, but I can't find a nice way to structure the
 282         // code and keep it DRY that accommodates that use case at the
 283         // moment.
 284
 285         let tcx = bcx.tcx();
 286         let closure_ty = expr_ty_adjusted(bcx, expr);
 287         debug!("add_env(closure_ty=%s)", closure_ty.repr(tcx));
 288         let scratch = scratch_datum(bcx, closure_ty, "__adjust", false);
 289         let llfn = GEPi(bcx, scratch.val, [0u, abi::fn_field_code]);
 290         assert_eq!(datum.appropriate_mode(tcx), ByValue);
 291         Store(bcx, datum.to_appropriate_llval(bcx), llfn);
 292         let llenv = GEPi(bcx, scratch.val, [0u, abi::fn_field_box]);
 293         Store(bcx, base::null_env_ptr(bcx.ccx()), llenv);
 294         DatumBlock {bcx: bcx, datum: scratch}
 295     }
 296
 297     fn auto_slice_and_ref(bcx: @mut Block,
 298                           autoderefs: uint,
 299                           expr: &ast::expr,
 300                           datum: Datum) -> DatumBlock {
 301         let DatumBlock { bcx, datum } = auto_slice(bcx, autoderefs, expr, datum);
 302         auto_ref(bcx, datum)
 303     }
 304
 305     fn auto_borrow_obj(mut bcx: @mut Block,
 306                        autoderefs: uint,
 307                        expr: @ast::expr,
 308                        source_datum: Datum) -> DatumBlock {
 309         let tcx = bcx.tcx();
 310         let target_obj_ty = expr_ty_adjusted(bcx, expr);
 311         debug!("auto_borrow_obj(target=%s)",
 312                target_obj_ty.repr(tcx));
 313         let scratch = scratch_datum(bcx, target_obj_ty,
 314                                     "__auto_borrow_obj", false);
 315
 316         // Convert a @Object, ~Object, or &Object pair into an &Object pair.
 317
 318         // Get a pointer to the source object, which is represented as
 319         // a (vtable, data) pair.
 320         let source_llval = source_datum.to_ref_llval(bcx);
 321
 322         // Set the vtable field of the new pair
 323         let vtable_ptr = GEPi(bcx, source_llval, [0u, abi::trt_field_vtable]);
 324         let vtable = Load(bcx, vtable_ptr);
 325         Store(bcx, vtable, GEPi(bcx, scratch.val, [0u, abi::trt_field_vtable]));
 326
 327         // Load the data for the source, which is either an @T,
 328         // ~T, or &T, depending on source_obj_ty.
 329         let source_data_ptr = GEPi(bcx, source_llval, [0u, abi::trt_field_box]);
 330         let source_data = Load(bcx, source_data_ptr); // always a ptr
 331         let (source_store, source_mutbl) = match ty::get(source_datum.ty).sty {
 332             ty::ty_trait(_, _, s, m, _) => (s, m),
 333             _ => {
 334                 bcx.sess().span_bug(
 335                     expr.span,
 336                     fmt!("auto_borrow_trait_obj expected a trait, found %s",
 337                          source_datum.ty.repr(bcx.tcx())));
 338             }
 339         };
 340         let target_data = match source_store {
 341             ty::BoxTraitStore(*) => {
 342                 // For deref of @T or @mut T, create a dummy datum and
 343                 // use the datum's deref method. This is more work
 344                 // than just calling GEPi ourselves, but it ensures
 345                 // that any write guards will be appropriate
 346                 // processed.  Note that we don't know the type T, so
 347                 // just substitute `i8`-- it doesn't really matter for
 348                 // our purposes right now.
 349                 let source_ty =
 350                     ty::mk_box(tcx,
 351                                ty::mt {
 352                                    ty: ty::mk_i8(),
 353                                    mutbl: source_mutbl});
 354                 let source_datum =
 355                     Datum {val: source_data,
 356                            ty: source_ty,
 357                            mode: ByValue};
 358                 let derefd_datum =
 359                     unpack_datum!(bcx,
 360                                   source_datum.deref(bcx,
 361                                                      expr,
 362                                                      autoderefs));
 363                 derefd_datum.to_rptr(bcx).to_value_llval(bcx)
 364             }
 365             ty::UniqTraitStore(*) => {
 366                 // For a ~T box, there may or may not be a header,
 367                 // depending on whether the type T references managed
 368                 // boxes. However, since we do not *know* the type T
 369                 // for objects, this presents a hurdle. Our solution is
 370                 // to load the "borrow offset" from the type descriptor;
 371                 // this value will either be 0 or sizeof(BoxHeader), depending
 372                 // on the type T.
 373                 let llopaque =
 374                     PointerCast(bcx, source_data, Type::opaque().ptr_to());
 375                 let lltydesc_ptr_ptr =
 376                     PointerCast(bcx, vtable,
 377                                 bcx.ccx().tydesc_type.ptr_to().ptr_to());
 378                 let lltydesc_ptr =
 379                     Load(bcx, lltydesc_ptr_ptr);
 380                 let borrow_offset_ptr =
 381                     GEPi(bcx, lltydesc_ptr,
 382                          [0, abi::tydesc_field_borrow_offset]);
 383                 let borrow_offset =
 384                     Load(bcx, borrow_offset_ptr);
 385                 InBoundsGEP(bcx, llopaque, [borrow_offset])
 386             }
 387             ty::RegionTraitStore(*) => {
 388                 source_data
 389             }
 390         };
 391         Store(bcx, target_data,
 392               GEPi(bcx, scratch.val, [0u, abi::trt_field_box]));
 393
 394         DatumBlock { bcx: bcx, datum: scratch }
 395     }
 396 }
 397
 398 pub fn trans_into(bcx: @mut Block, expr: @ast::expr, dest: Dest) -> @mut Block {
 399     if bcx.tcx().adjustments.contains_key(&expr.id) {
 400         // use trans_to_datum, which is mildly less efficient but
 401         // which will perform the adjustments:
 402         let datumblock = trans_to_datum(bcx, expr);
 403         return match dest {
 404             Ignore => datumblock.bcx,
 405             SaveIn(lldest) => datumblock.store_to(INIT, lldest)
 406         };
 407     }
 408
 409     let ty = expr_ty(bcx, expr);
 410
 411     debug!("trans_into_unadjusted(expr=%s, dest=%s)",
 412            bcx.expr_to_str(expr),
 413            dest.to_str(bcx.ccx()));
 414     let _indenter = indenter();
 415
 416     debuginfo::update_source_pos(bcx.fcx, expr.id, expr.span);
 417
 418     let dest = {
 419         if ty::type_is_voidish(ty) {
 420             Ignore
 421         } else {
 422             dest
 423         }
 424     };
 425
 426     let kind = bcx.expr_kind(expr);
 427     debug!("expr kind = %?", kind);
 428     return match kind {
 429         ty::LvalueExpr => {
 430             let datumblock = trans_lvalue_unadjusted(bcx, expr);
 431             match dest {
 432                 Ignore => datumblock.bcx,
 433                 SaveIn(lldest) => datumblock.store_to(INIT, lldest)
 434             }
 435         }
 436         ty::RvalueDatumExpr => {
 437             let datumblock = trans_rvalue_datum_unadjusted(bcx, expr);
 438             match dest {
 439                 Ignore => datumblock.drop_val(),
 440
 441                 // When processing an rvalue, the value will be newly
 442                 // allocated, so we always `move_to` so as not to
 443                 // unnecessarily inc ref counts and so forth:
 444                 SaveIn(lldest) => datumblock.move_to(INIT, lldest)
 445             }
 446         }
 447         ty::RvalueDpsExpr => {
 448             trans_rvalue_dps_unadjusted(bcx, expr, dest)
 449         }
 450         ty::RvalueStmtExpr => {
 451             trans_rvalue_stmt_unadjusted(bcx, expr)
 452         }
 453     };
 454 }
 455
 456 fn trans_lvalue(bcx: @mut Block, expr: @ast::expr) -> DatumBlock {
 457     /*!
 458      *
 459      * Translates an lvalue expression, always yielding a by-ref
 460      * datum.  Generally speaking you should call trans_to_datum()
 461      * instead, but sometimes we call trans_lvalue() directly as a
 462      * means of asserting that a particular expression is an lvalue. */
 463
 464     return match bcx.tcx().adjustments.find(&expr.id) {
 465         None => trans_lvalue_unadjusted(bcx, expr),
 466         Some(_) => {
 467             bcx.sess().span_bug(
 468                 expr.span,
 469                 fmt!("trans_lvalue() called on an expression \
 470                       with adjustments"));
 471         }
 472     };
 473 }
 474
 475 fn trans_to_datum_unadjusted(bcx: @mut Block, expr: @ast::expr) -> DatumBlock {
 476     /*!
 477      * Translates an expression into a datum.  If this expression
 478      * is an rvalue, this will result in a temporary value being
 479      * created.  If you plan to store the value somewhere else,
 480      * you should prefer `trans_into()` instead.
 481      */
 482
 483     let mut bcx = bcx;
 484
 485     debug!("trans_to_datum_unadjusted(expr=%s)", bcx.expr_to_str(expr));
 486     let _indenter = indenter();
 487
 488     debuginfo::update_source_pos(bcx.fcx, expr.id, expr.span);
 489
 490     match ty::expr_kind(bcx.tcx(), bcx.ccx().maps.method_map, expr) {
 491         ty::LvalueExpr => {
 492             return trans_lvalue_unadjusted(bcx, expr);
 493         }
 494
 495         ty::RvalueDatumExpr => {
 496             let datum = unpack_datum!(bcx, {
 497                 trans_rvalue_datum_unadjusted(bcx, expr)
 498             });
 499             datum.add_clean(bcx);
 500             return DatumBlock {bcx: bcx, datum: datum};
 501         }
 502
 503         ty::RvalueStmtExpr => {
 504             bcx = trans_rvalue_stmt_unadjusted(bcx, expr);
 505             return nil(bcx, expr_ty(bcx, expr));
 506         }
 507
 508         ty::RvalueDpsExpr => {
 509             let ty = expr_ty(bcx, expr);
 510             if ty::type_is_voidish(ty) {
 511                 bcx = trans_rvalue_dps_unadjusted(bcx, expr, Ignore);
 512                 return nil(bcx, ty);
 513             } else {
 514                 let scratch = scratch_datum(bcx, ty, "", false);
 515                 bcx = trans_rvalue_dps_unadjusted(
 516                     bcx, expr, SaveIn(scratch.val));
 517
 518                 // Note: this is not obviously a good idea.  It causes
 519                 // immediate values to be loaded immediately after a
 520                 // return from a call or other similar expression,
 521                 // which in turn leads to alloca's having shorter
 522                 // lifetimes and hence larger stack frames.  However,
 523                 // in turn it can lead to more register pressure.
 524                 // Still, in practice it seems to increase
 525                 // performance, since we have fewer problems with
 526                 // morestack churn.
 527                 let scratch = scratch.to_appropriate_datum(bcx);
 528
 529                 scratch.add_clean(bcx);
 530                 return DatumBlock {bcx: bcx, datum: scratch};
 531             }
 532         }
 533     }
 534
 535     fn nil(bcx: @mut Block, ty: ty::t) -> DatumBlock {
 536         let datum = immediate_rvalue(C_nil(), ty);
 537         DatumBlock {bcx: bcx, datum: datum}
 538     }
 539 }
 540
 541 fn trans_rvalue_datum_unadjusted(bcx: @mut Block, expr: @ast::expr) -> DatumBlock {
 542     let _icx = push_ctxt("trans_rvalue_datum_unadjusted");
 543
 544     trace_span!(bcx, expr.span, shorten(bcx.expr_to_str(expr)));
 545
 546     match expr.node {
 547         ast::expr_path(_) | ast::expr_self => {
 548             return trans_def_datum_unadjusted(bcx, expr, bcx.def(expr.id));
 549         }
 550         ast::expr_vstore(contents, ast::expr_vstore_box) |
 551         ast::expr_vstore(contents, ast::expr_vstore_mut_box) => {
 552             return tvec::trans_uniq_or_managed_vstore(bcx, heap_managed,
 553                                                       expr, contents);
 554         }
 555         ast::expr_vstore(contents, ast::expr_vstore_uniq) => {
 556             let heap = heap_for_unique(bcx, expr_ty(bcx, contents));
 557             return tvec::trans_uniq_or_managed_vstore(bcx, heap,
 558                                                       expr, contents);
 559         }
 560         ast::expr_lit(lit) => {
 561             return trans_immediate_lit(bcx, expr, *lit);
 562         }
 563         ast::expr_binary(_, op, lhs, rhs) => {
 564             // if overloaded, would be RvalueDpsExpr
 565             assert!(!bcx.ccx().maps.method_map.contains_key(&expr.id));
 566
 567             return trans_binary(bcx, expr, op, lhs, rhs);
 568         }
 569         ast::expr_unary(_, op, x) => {
 570             return trans_unary_datum(bcx, expr, op, x);
 571         }
 572         ast::expr_addr_of(_, x) => {
 573             return trans_addr_of(bcx, expr, x);
 574         }
 575         ast::expr_cast(val, _) => {
 576             return trans_imm_cast(bcx, val, expr.id);
 577         }
 578         ast::expr_paren(e) => {
 579             return trans_rvalue_datum_unadjusted(bcx, e);
 580         }
 581         _ => {
 582             bcx.tcx().sess.span_bug(
 583                 expr.span,
 584                 fmt!("trans_rvalue_datum_unadjusted reached \
 585                       fall-through case: %?",
 586                      expr.node));
 587         }
 588     }
 589 }
 590
 591 fn trans_rvalue_stmt_unadjusted(bcx: @mut Block, expr: @ast::expr) -> @mut Block {
 592     let mut bcx = bcx;
 593     let _icx = push_ctxt("trans_rvalue_stmt");
 594
 595     if bcx.unreachable {
 596         return bcx;
 597     }
 598
 599     trace_span!(bcx, expr.span, shorten(bcx.expr_to_str(expr)));
 600
 601     match expr.node {
 602         ast::expr_break(label_opt) => {
 603             return controlflow::trans_break(bcx, label_opt);
 604         }
 605         ast::expr_again(label_opt) => {
 606             return controlflow::trans_cont(bcx, label_opt);
 607         }
 608         ast::expr_ret(ex) => {
 609             return controlflow::trans_ret(bcx, ex);
 610         }
 611         ast::expr_log(lvl, a) => {
 612             return controlflow::trans_log(expr, lvl, bcx, a);
 613         }
 614         ast::expr_while(cond, ref body) => {
 615             return controlflow::trans_while(bcx, cond, body);
 616         }
 617         ast::expr_loop(ref body, opt_label) => {
 618             return controlflow::trans_loop(bcx, body, opt_label);
 619         }
 620         ast::expr_assign(dst, src) => {
 621             let src_datum = unpack_datum!(
 622                 bcx, trans_to_datum(bcx, src));
 623             let dst_datum = unpack_datum!(
 624                 bcx, trans_lvalue(bcx, dst));
 625             return src_datum.store_to_datum(
 626                 bcx, DROP_EXISTING, dst_datum);
 627         }
 628         ast::expr_assign_op(callee_id, op, dst, src) => {
 629             return trans_assign_op(bcx, expr, callee_id, op, dst, src);
 630         }
 631         ast::expr_paren(a) => {
 632             return trans_rvalue_stmt_unadjusted(bcx, a);
 633         }
 634         ast::expr_inline_asm(ref a) => {
 635             return asm::trans_inline_asm(bcx, a);
 636         }
 637         _ => {
 638             bcx.tcx().sess.span_bug(
 639                 expr.span,
 640                 fmt!("trans_rvalue_stmt_unadjusted reached \
 641                       fall-through case: %?",
 642                      expr.node));
 643         }
 644     };
 645 }
 646
 647 fn trans_rvalue_dps_unadjusted(bcx: @mut Block, expr: @ast::expr,
 648                                dest: Dest) -> @mut Block {
 649     let _icx = push_ctxt("trans_rvalue_dps_unadjusted");
 650     let tcx = bcx.tcx();
 651
 652     trace_span!(bcx, expr.span, shorten(bcx.expr_to_str(expr)));
 653
 654     match expr.node {
 655         ast::expr_paren(e) => {
 656             return trans_rvalue_dps_unadjusted(bcx, e, dest);
 657         }
 658         ast::expr_path(_) | ast::expr_self => {
 659             return trans_def_dps_unadjusted(bcx, expr,
 660                                             bcx.def(expr.id), dest);
 661         }
 662         ast::expr_if(cond, ref thn, els) => {
 663             return controlflow::trans_if(bcx, cond, thn, els, dest);
 664         }
 665         ast::expr_match(discr, ref arms) => {
 666             return _match::trans_match(bcx, expr, discr, *arms, dest);
 667         }
 668         ast::expr_block(ref blk) => {
 669             return do base::with_scope(bcx, blk.info(),
 670                                        "block-expr body") |bcx| {
 671                 controlflow::trans_block(bcx, blk, dest)
 672             };
 673         }
 674         ast::expr_struct(_, ref fields, base) => {
 675             return trans_rec_or_struct(bcx, (*fields), base, expr.span, expr.id, dest);
 676         }
 677         ast::expr_tup(ref args) => {
 678             let repr = adt::represent_type(bcx.ccx(), expr_ty(bcx, expr));
 679             let numbered_fields: ~[(uint, @ast::expr)] =
 680                 args.iter().enumerate().map(|(i, arg)| (i, *arg)).collect();
 681             return trans_adt(bcx, repr, 0, numbered_fields, None, dest);
 682         }
 683         ast::expr_lit(@codemap::spanned {node: ast::lit_str(s), _}) => {
 684             return tvec::trans_lit_str(bcx, expr, s, dest);
 685         }
 686         ast::expr_vstore(contents, ast::expr_vstore_slice) |
 687         ast::expr_vstore(contents, ast::expr_vstore_mut_slice) => {
 688             return tvec::trans_slice_vstore(bcx, expr, contents, dest);
 689         }
 690         ast::expr_vec(*) | ast::expr_repeat(*) => {
 691             return tvec::trans_fixed_vstore(bcx, expr, expr, dest);
 692         }
 693         ast::expr_fn_block(ref decl, ref body) => {
 694             let expr_ty = expr_ty(bcx, expr);
 695             let sigil = ty::ty_closure_sigil(expr_ty);
 696             debug!("translating fn_block %s with type %s",
 697                    expr_to_str(expr, tcx.sess.intr()),
 698                    expr_ty.repr(tcx));
 699             return closure::trans_expr_fn(bcx, sigil, decl, body,
 700                                           expr.id, expr.id, dest);
 701         }
 702         ast::expr_do_body(blk) => {
 703             return trans_into(bcx, blk, dest);
 704         }
 705         ast::expr_call(f, ref args, _) => {
 706             return callee::trans_call(
 707                 bcx, expr, f, callee::ArgExprs(*args), expr.id, dest);
 708         }
 709         ast::expr_method_call(callee_id, rcvr, _, _, ref args, _) => {
 710             return callee::trans_method_call(bcx,
 711                                              expr,
 712                                              callee_id,
 713                                              rcvr,
 714                                              callee::ArgExprs(*args),
 715                                              dest);
 716         }
 717         ast::expr_binary(callee_id, _, lhs, rhs) => {
 718             // if not overloaded, would be RvalueDatumExpr
 719             return trans_overloaded_op(bcx,
 720                                        expr,
 721                                        callee_id,
 722                                        lhs,
 723                                        ~[rhs],
 724                                        expr_ty(bcx, expr),
 725                                        dest);
 726         }
 727         ast::expr_unary(callee_id, _, subexpr) => {
 728             // if not overloaded, would be RvalueDatumExpr
 729             return trans_overloaded_op(bcx,
 730                                        expr,
 731                                        callee_id,
 732                                        subexpr,
 733                                        ~[],
 734                                        expr_ty(bcx, expr),
 735                                        dest);
 736         }
 737         ast::expr_index(callee_id, base, idx) => {
 738             // if not overloaded, would be RvalueDatumExpr
 739             return trans_overloaded_op(bcx,
 740                                        expr,
 741                                        callee_id,
 742                                        base,
 743                                        ~[idx],
 744                                        expr_ty(bcx, expr),
 745                                        dest);
 746         }
 747         ast::expr_cast(val, _) => {
 748             match ty::get(node_id_type(bcx, expr.id)).sty {
 749                 ty::ty_trait(_, _, store, _, _) => {
 750                     return meth::trans_trait_cast(bcx, val, expr.id, dest,
 751                                                   store);
 752                 }
 753                 _ => {
 754                     bcx.tcx().sess.span_bug(expr.span,
 755                                             "expr_cast of non-trait");
 756                 }
 757             }
 758         }
 759         ast::expr_assign_op(callee_id, op, dst, src) => {
 760             return trans_assign_op(bcx, expr, callee_id, op, dst, src);
 761         }
 762         _ => {
 763             bcx.tcx().sess.span_bug(
 764                 expr.span,
 765                 fmt!("trans_rvalue_dps_unadjusted reached fall-through case: %?",
 766                      expr.node));
 767         }
 768     }
 769 }
 770
 771 fn trans_def_dps_unadjusted(bcx: @mut Block, ref_expr: &ast::expr,
 772                             def: ast::def, dest: Dest) -> @mut Block {
 773     let _icx = push_ctxt("trans_def_dps_unadjusted");
 774     let ccx = bcx.ccx();
 775
 776     let lldest = match dest {
 777         SaveIn(lldest) => lldest,
 778         Ignore => { return bcx; }
 779     };
 780
 781     match def {
 782         ast::def_variant(tid, vid) => {
 783             let variant_info = ty::enum_variant_with_id(ccx.tcx, tid, vid);
 784             if variant_info.args.len() > 0u {
 785                 // N-ary variant.
 786                 let fn_data = callee::trans_fn_ref(bcx, vid, ref_expr.id);
 787                 Store(bcx, fn_data.llfn, lldest);
 788                 return bcx;
 789             } else {
 790                 // Nullary variant.
 791                 let ty = expr_ty(bcx, ref_expr);
 792                 let repr = adt::represent_type(ccx, ty);
 793                 adt::trans_start_init(bcx, repr, lldest,
 794                                       variant_info.disr_val);
 795                 return bcx;
 796             }
 797         }
 798         ast::def_struct(def_id) => {
 799             let ty = expr_ty(bcx, ref_expr);
 800             match ty::get(ty).sty {
 801                 ty::ty_struct(did, _) if ty::has_dtor(ccx.tcx, did) => {
 802                     let repr = adt::represent_type(ccx, ty);
 803                     adt::trans_start_init(bcx, repr, lldest, 0);
 804                 }
 805                 ty::ty_bare_fn(*) => {
 806                     let fn_data = callee::trans_fn_ref(bcx, def_id, ref_expr.id);
 807                     Store(bcx, fn_data.llfn, lldest);
 808                 }
 809                 _ => ()
 810             }
 811             return bcx;
 812         }
 813         _ => {
 814             bcx.tcx().sess.span_bug(ref_expr.span, fmt!(
 815                 "Non-DPS def %? referened by %s",
 816                 def, bcx.node_id_to_str(ref_expr.id)));
 817         }
 818     }
 819 }
 820
 821 fn trans_def_datum_unadjusted(bcx: @mut Block,
 822                               ref_expr: &ast::expr,
 823                               def: ast::def) -> DatumBlock
 824 {
 825     let _icx = push_ctxt("trans_def_datum_unadjusted");
 826
 827     match def {
 828         ast::def_fn(did, _) | ast::def_static_method(did, None, _) => {
 829             let fn_data = callee::trans_fn_ref(bcx, did, ref_expr.id);
 830             return fn_data_to_datum(bcx, ref_expr, did, fn_data);
 831         }
 832         ast::def_static_method(impl_did, Some(trait_did), _) => {
 833             let fn_data = meth::trans_static_method_callee(bcx, impl_did,
 834                                                            trait_did,
 835                                                            ref_expr.id);
 836             return fn_data_to_datum(bcx, ref_expr, impl_did, fn_data);
 837         }
 838         _ => {
 839             bcx.tcx().sess.span_bug(ref_expr.span, fmt!(
 840                 "Non-DPS def %? referened by %s",
 841                 def, bcx.node_id_to_str(ref_expr.id)));
 842         }
 843     }
 844
 845     fn fn_data_to_datum(bcx: @mut Block,
 846                         ref_expr: &ast::expr,
 847                         def_id: ast::def_id,
 848                         fn_data: callee::FnData) -> DatumBlock {
 849         /*!
 850         *
 851         * Translates a reference to a top-level fn item into a rust
 852         * value.  This is just a fn pointer.
 853         */
 854
 855         let is_extern = {
 856             let fn_tpt = ty::lookup_item_type(bcx.tcx(), def_id);
 857             ty::ty_fn_purity(fn_tpt.ty) == ast::extern_fn
 858         };
 859         let (rust_ty, llval) = if is_extern {
 860             let rust_ty = ty::mk_ptr(
 861                 bcx.tcx(),
 862                 ty::mt {
 863                     ty: ty::mk_mach_uint(ast::ty_u8),
 864                     mutbl: ast::m_imm
 865                 }); // *u8
 866             (rust_ty, PointerCast(bcx, fn_data.llfn, Type::i8p()))
 867         } else {
 868             let fn_ty = expr_ty(bcx, ref_expr);
 869             (fn_ty, fn_data.llfn)
 870         };
 871         return DatumBlock {
 872             bcx: bcx,
 873             datum: Datum {val: llval,
 874                           ty: rust_ty,
 875                           mode: ByValue}
 876         };
 877     }
 878 }
 879
 880 fn trans_lvalue_unadjusted(bcx: @mut Block, expr: @ast::expr) -> DatumBlock {
 881     /*!
 882      *
 883      * Translates an lvalue expression, always yielding a by-ref
 884      * datum.  Does not apply any adjustments. */
 885
 886     let _icx = push_ctxt("trans_lval");
 887     let mut bcx = bcx;
 888
 889     debug!("trans_lvalue(expr=%s)", bcx.expr_to_str(expr));
 890     let _indenter = indenter();
 891
 892     trace_span!(bcx, expr.span, shorten(bcx.expr_to_str(expr)));
 893
 894     return match expr.node {
 895         ast::expr_paren(e) => {
 896             trans_lvalue_unadjusted(bcx, e)
 897         }
 898         ast::expr_path(_) | ast::expr_self => {
 899             trans_def_lvalue(bcx, expr, bcx.def(expr.id))
 900         }
 901         ast::expr_field(base, ident, _) => {
 902             trans_rec_field(bcx, base, ident)
 903         }
 904         ast::expr_index(_, base, idx) => {
 905             trans_index(bcx, expr, base, idx)
 906         }
 907         ast::expr_unary(_, ast::deref, base) => {
 908             let basedatum = unpack_datum!(bcx, trans_to_datum(bcx, base));
 909             basedatum.deref(bcx, expr, 0)
 910         }
 911         _ => {
 912             bcx.tcx().sess.span_bug(
 913                 expr.span,
 914                 fmt!("trans_lvalue reached fall-through case: %?",
 915                      expr.node));
 916         }
 917     };
 918
 919     fn trans_rec_field(bcx: @mut Block,
 920                        base: @ast::expr,
 921                        field: ast::ident) -> DatumBlock {
 922         //! Translates `base.field`.
 923
 924         let mut bcx = bcx;
 925         let _icx = push_ctxt("trans_rec_field");
 926
 927         let base_datum = unpack_datum!(bcx, trans_to_datum(bcx, base));
 928         let repr = adt::represent_type(bcx.ccx(), base_datum.ty);
 929         do with_field_tys(bcx.tcx(), base_datum.ty, None) |discr, field_tys| {
 930             let ix = ty::field_idx_strict(bcx.tcx(), field, field_tys);
 931             DatumBlock {
 932                 datum: do base_datum.get_element(bcx,
 933                                                  field_tys[ix].mt.ty,
 934                                                  ZeroMem) |srcval| {
 935                     adt::trans_field_ptr(bcx, repr, srcval, discr, ix)
 936                 },
 937                 bcx: bcx
 938             }
 939         }
 940     }
 941
 942     fn trans_index(bcx: @mut Block,
 943                    index_expr: &ast::expr,
 944                    base: @ast::expr,
 945                    idx: @ast::expr) -> DatumBlock {
 946         //! Translates `base[idx]`.
 947
 948         let _icx = push_ctxt("trans_index");
 949         let ccx = bcx.ccx();
 950         let mut bcx = bcx;
 951
 952         let base_datum = unpack_datum!(bcx, trans_to_datum(bcx, base));
 953
 954         // Translate index expression and cast to a suitable LLVM integer.
 955         // Rust is less strict than LLVM in this regard.
 956         let Result {bcx, val: ix_val} = trans_to_datum(bcx, idx).to_result();
 957         let ix_size = machine::llbitsize_of_real(bcx.ccx(), val_ty(ix_val));
 958         let int_size = machine::llbitsize_of_real(bcx.ccx(), ccx.int_type);
 959         let ix_val = {
 960             if ix_size < int_size {
 961                 if ty::type_is_signed(expr_ty(bcx, idx)) {
 962                     SExt(bcx, ix_val, ccx.int_type)
 963                 } else { ZExt(bcx, ix_val, ccx.int_type) }
 964             } else if ix_size > int_size {
 965                 Trunc(bcx, ix_val, ccx.int_type)
 966             } else {
 967                 ix_val
 968             }
 969         };
 970
 971         let vt = tvec::vec_types(bcx, base_datum.ty);
 972         base::maybe_name_value(bcx.ccx(), vt.llunit_size, "unit_sz");
 973         let scaled_ix = Mul(bcx, ix_val, vt.llunit_size);
 974         base::maybe_name_value(bcx.ccx(), scaled_ix, "scaled_ix");
 975
 976         let (bcx, base, len) =
 977             base_datum.get_vec_base_and_len(bcx, index_expr.span,
 978                                             index_expr.id, 0);
 979
 980         debug!("trans_index: base %s", bcx.val_to_str(base));
 981         debug!("trans_index: len %s", bcx.val_to_str(len));
 982
 983         let bounds_check = ICmp(bcx, lib::llvm::IntUGE, scaled_ix, len);
 984         let bcx = do with_cond(bcx, bounds_check) |bcx| {
 985             let unscaled_len = UDiv(bcx, len, vt.llunit_size);
 986             controlflow::trans_fail_bounds_check(bcx, index_expr.span,
 987                                                  ix_val, unscaled_len)
 988         };
 989         let elt = InBoundsGEP(bcx, base, [ix_val]);
 990         let elt = PointerCast(bcx, elt, vt.llunit_ty.ptr_to());
 991         return DatumBlock {
 992             bcx: bcx,
 993             datum: Datum {val: elt,
 994                           ty: vt.unit_ty,
 995                           mode: ByRef(ZeroMem)}
 996         };
 997     }
 998
 999     fn trans_def_lvalue(bcx: @mut Block,
1000                         ref_expr: &ast::expr,
1001                         def: ast::def)
1002         -> DatumBlock
1003     {
1004         //! Translates a reference to a path.
1005
1006         let _icx = push_ctxt("trans_def_lvalue");
1007         match def {
1008             ast::def_static(did, _) => {
1009                 let const_ty = expr_ty(bcx, ref_expr);
1010
1011                 fn get_val(bcx: @mut Block, did: ast::def_id, const_ty: ty::t)
1012                            -> ValueRef {
1013                     // For external constants, we don't inline.
1014                     if did.crate == ast::LOCAL_CRATE {
1015                         // The LLVM global has the type of its initializer,
1016                         // which may not be equal to the enum's type for
1017                         // non-C-like enums.
1018                         let val = base::get_item_val(bcx.ccx(), did.node);
1019                         let pty = type_of(bcx.ccx(), const_ty).ptr_to();
1020                         PointerCast(bcx, val, pty)
1021                     } else {
1022                         {
1023                             let extern_const_values = &bcx.ccx().extern_const_values;
1024                             match extern_const_values.find(&did) {
1025                                 None => {}  // Continue.
1026                                 Some(llval) => {
1027                                     return *llval;
1028                                 }
1029                             }
1030                         }
1031
1032                         unsafe {
1033                             let llty = type_of(bcx.ccx(), const_ty);
1034                             let symbol = csearch::get_symbol(
1035                                 bcx.ccx().sess.cstore,
1036                                 did);
1037                             let llval = do symbol.with_c_str |buf| {
1038                                 llvm::LLVMAddGlobal(bcx.ccx().llmod,
1039                                                     llty.to_ref(),
1040                                                     buf)
1041                             };
1042                             SetLinkage(llval, ExternalLinkage);
1043                             let extern_const_values = &mut bcx.ccx().extern_const_values;
1044                             extern_const_values.insert(did, llval);
1045                             llval
1046                         }
1047                     }
1048                 }
1049
1050                 let val = get_val(bcx, did, const_ty);
1051                 DatumBlock {
1052                     bcx: bcx,
1053                     datum: Datum {val: val,
1054                                   ty: const_ty,
1055                                   mode: ByRef(ZeroMem)}
1056                 }
1057             }
1058             _ => {
1059                 DatumBlock {
1060                     bcx: bcx,
1061                     datum: trans_local_var(bcx, def)
1062                 }
1063             }
1064         }
1065     }
1066 }
1067
1068 pub fn trans_local_var(bcx: @mut Block, def: ast::def) -> Datum {
1069     let _icx = push_ctxt("trans_local_var");
1070
1071     return match def {
1072         ast::def_upvar(nid, _, _, _) => {
1073             // Can't move upvars, so this is never a ZeroMemLastUse.
1074             let local_ty = node_id_type(bcx, nid);
1075             match bcx.fcx.llupvars.find(&nid) {
1076                 Some(&val) => {
1077                     Datum {
1078                         val: val,
1079                         ty: local_ty,
1080                         mode: ByRef(ZeroMem)
1081                     }
1082                 }
1083                 None => {
1084                     bcx.sess().bug(fmt!(
1085                         "trans_local_var: no llval for upvar %? found", nid));
1086                 }
1087             }
1088         }
1089         ast::def_arg(nid, _) => {
1090             take_local(bcx, bcx.fcx.llargs, nid)
1091         }
1092         ast::def_local(nid, _) | ast::def_binding(nid, _) => {
1093             take_local(bcx, bcx.fcx.lllocals, nid)
1094         }
1095         ast::def_self(nid, _) => {
1096             let self_info: ValSelfData = match bcx.fcx.llself {
1097                 Some(ref self_info) => *self_info,
1098                 None => {
1099                     bcx.sess().bug(fmt!(
1100                         "trans_local_var: reference to self \
1101                          out of context with id %?", nid));
1102                 }
1103             };
1104
1105             debug!("def_self() reference, self_info.t=%s",
1106                    self_info.t.repr(bcx.tcx()));
1107
1108             Datum {
1109                 val: self_info.v,
1110                 ty: self_info.t,
1111                 mode: ByRef(ZeroMem)
1112             }
1113         }
1114         _ => {
1115             bcx.sess().unimpl(fmt!(
1116                 "unsupported def type in trans_local_var: %?", def));
1117         }
1118     };
1119
1120     fn take_local(bcx: @mut Block,
1121                   table: &HashMap<ast::NodeId, ValueRef>,
1122                   nid: ast::NodeId) -> Datum {
1123         let v = match table.find(&nid) {
1124             Some(&v) => v,
1125             None => {
1126                 bcx.sess().bug(fmt!(
1127                     "trans_local_var: no llval for local/arg %? found", nid));
1128             }
1129         };
1130         let ty = node_id_type(bcx, nid);
1131         debug!("take_local(nid=%?, v=%s, ty=%s)",
1132                nid, bcx.val_to_str(v), bcx.ty_to_str(ty));
1133         Datum {
1134             val: v,
1135             ty: ty,
1136             mode: ByRef(ZeroMem)
1137         }
1138     }
1139 }
1140
1141 // The optional node ID here is the node ID of the path identifying the enum
1142 // variant in use. If none, this cannot possibly an enum variant (so, if it
1143 // is and `node_id_opt` is none, this function fails).
1144 pub fn with_field_tys<R>(tcx: ty::ctxt,
1145                          ty: ty::t,
1146                          node_id_opt: Option<ast::NodeId>,
1147                          op: &fn(uint, (&[ty::field])) -> R) -> R {
1148     match ty::get(ty).sty {
1149         ty::ty_struct(did, ref substs) => {
1150             op(0, struct_fields(tcx, did, substs))
1151         }
1152
1153         ty::ty_enum(_, ref substs) => {
1154             // We want the *variant* ID here, not the enum ID.
1155             match node_id_opt {
1156                 None => {
1157                     tcx.sess.bug(fmt!(
1158                         "cannot get field types from the enum type %s \
1159                          without a node ID",
1160                         ty.repr(tcx)));
1161                 }
1162                 Some(node_id) => {
1163                     match tcx.def_map.get_copy(&node_id) {
1164                         ast::def_variant(enum_id, variant_id) => {
1165                             let variant_info = ty::enum_variant_with_id(
1166                                 tcx, enum_id, variant_id);
1167                             op(variant_info.disr_val,
1168                                struct_fields(tcx, variant_id, substs))
1169                         }
1170                         _ => {
1171                             tcx.sess.bug("resolve didn't map this expr to a \
1172                                           variant ID")
1173                         }
1174                     }
1175                 }
1176             }
1177         }
1178
1179         _ => {
1180             tcx.sess.bug(fmt!(
1181                 "cannot get field types from the type %s",
1182                 ty.repr(tcx)));
1183         }
1184     }
1185 }
1186
1187 fn trans_rec_or_struct(bcx: @mut Block,
1188                        fields: &[ast::Field],
1189                        base: Option<@ast::expr>,
1190                        expr_span: codemap::span,
1191                        id: ast::NodeId,
1192                        dest: Dest) -> @mut Block
1193 {
1194     let _icx = push_ctxt("trans_rec");
1195     let bcx = bcx;
1196
1197     let ty = node_id_type(bcx, id);
1198     let tcx = bcx.tcx();
1199     do with_field_tys(tcx, ty, Some(id)) |discr, field_tys| {
1200         let mut need_base = vec::from_elem(field_tys.len(), true);
1201
1202         let numbered_fields = do fields.map |field| {
1203             let opt_pos = field_tys.iter().position(|field_ty| field_ty.ident == field.ident);
1204             match opt_pos {
1205                 Some(i) => {
1206                     need_base[i] = false;
1207                     (i, field.expr)
1208                 }
1209                 None => {
1210                     tcx.sess.span_bug(field.span,
1211                                       "Couldn't find field in struct type")
1212                 }
1213             }
1214         };
1215         let optbase = match base {
1216             Some(base_expr) => {
1217                 let mut leftovers = ~[];
1218                 for (i, b) in need_base.iter().enumerate() {
1219                     if *b {
1220                         leftovers.push((i, field_tys[i].mt.ty))
1221                     }
1222                 }
1223                 Some(StructBaseInfo {expr: base_expr,
1224                                      fields: leftovers })
1225             }
1226             None => {
1227                 if need_base.iter().any(|b| *b) {
1228                     tcx.sess.span_bug(expr_span, "missing fields and no base expr")
1229                 }
1230                 None
1231             }
1232         };
1233
1234         let repr = adt::represent_type(bcx.ccx(), ty);
1235         trans_adt(bcx, repr, discr, numbered_fields, optbase, dest)
1236     }
1237 }
1238
1239 /**
1240  * Information that `trans_adt` needs in order to fill in the fields
1241  * of a struct copied from a base struct (e.g., from an expression
1242  * like `Foo { a: b, ..base }`.
1243  *
1244  * Note that `fields` may be empty; the base expression must always be
1245  * evaluated for side-effects.
1246  */
1247 struct StructBaseInfo {
1248     /// The base expression; will be evaluated after all explicit fields.
1249     expr: @ast::expr,
1250     /// The indices of fields to copy paired with their types.
1251     fields: ~[(uint, ty::t)]
1252 }
1253
1254 /**
1255  * Constructs an ADT instance:
1256  *
1257  * - `fields` should be a list of field indices paired with the
1258  * expression to store into that field.  The initializers will be
1259  * evaluated in the order specified by `fields`.
1260  *
1261  * - `optbase` contains information on the base struct (if any) from
1262  * which remaining fields are copied; see comments on `StructBaseInfo`.
1263  */
1264 fn trans_adt(bcx: @mut Block, repr: &adt::Repr, discr: uint,
1265              fields: &[(uint, @ast::expr)],
1266              optbase: Option<StructBaseInfo>,
1267              dest: Dest) -> @mut Block {
1268     let _icx = push_ctxt("trans_adt");
1269     let mut bcx = bcx;
1270     let addr = match dest {
1271         Ignore => {
1272             for &(_i, e) in fields.iter() {
1273                 bcx = trans_into(bcx, e, Ignore);
1274             }
1275             for sbi in optbase.iter() {
1276                 // FIXME #7261: this moves entire base, not just certain fields
1277                 bcx = trans_into(bcx, sbi.expr, Ignore);
1278             }
1279             return bcx;
1280         }
1281         SaveIn(pos) => pos
1282     };
1283     let mut temp_cleanups = ~[];
1284     adt::trans_start_init(bcx, repr, addr, discr);
1285     for &(i, e) in fields.iter() {
1286         let dest = adt::trans_field_ptr(bcx, repr, addr, discr, i);
1287         let e_ty = expr_ty(bcx, e);
1288         bcx = trans_into(bcx, e, SaveIn(dest));
1289         add_clean_temp_mem(bcx, dest, e_ty);
1290         temp_cleanups.push(dest);
1291     }
1292     for base in optbase.iter() {
1293         // FIXME #6573: is it sound to use the destination's repr on the base?
1294         // And, would it ever be reasonable to be here with discr != 0?
1295         let base_datum = unpack_datum!(bcx, trans_to_datum(bcx, base.expr));
1296         for &(i, t) in base.fields.iter() {
1297             let datum = do base_datum.get_element(bcx, t, ZeroMem) |srcval| {
1298                 adt::trans_field_ptr(bcx, repr, srcval, discr, i)
1299             };
1300             let dest = adt::trans_field_ptr(bcx, repr, addr, discr, i);
1301             bcx = datum.store_to(bcx, INIT, dest);
1302         }
1303     }
1304
1305     for cleanup in temp_cleanups.iter() {
1306         revoke_clean(bcx, *cleanup);
1307     }
1308     return bcx;
1309 }
1310
1311
1312 fn trans_immediate_lit(bcx: @mut Block, expr: @ast::expr,
1313                        lit: ast::lit) -> DatumBlock {
1314     // must not be a string constant, that is a RvalueDpsExpr
1315     let _icx = push_ctxt("trans_immediate_lit");
1316     let ty = expr_ty(bcx, expr);
1317     immediate_rvalue_bcx(bcx, consts::const_lit(bcx.ccx(), expr, lit), ty)
1318 }
1319
1320 fn trans_unary_datum(bcx: @mut Block,
1321                      un_expr: &ast::expr,
1322                      op: ast::unop,
1323                      sub_expr: @ast::expr) -> DatumBlock {
1324     let _icx = push_ctxt("trans_unary_datum");
1325
1326     // if deref, would be LvalueExpr
1327     assert!(op != ast::deref);
1328
1329     // if overloaded, would be RvalueDpsExpr
1330     assert!(!bcx.ccx().maps.method_map.contains_key(&un_expr.id));
1331
1332     let un_ty = expr_ty(bcx, un_expr);
1333     let sub_ty = expr_ty(bcx, sub_expr);
1334
1335     return match op {
1336         ast::not => {
1337             let Result {bcx, val} = trans_to_datum(bcx, sub_expr).to_result();
1338
1339             // If this is a boolean type, we must not use the LLVM Not
1340             // instruction, as that is a *bitwise* not and we want *logical*
1341             // not on our 8-bit boolean values.
1342             let llresult = match ty::get(un_ty).sty {
1343                 ty::ty_bool => {
1344                     let llcond = ICmp(bcx,
1345                                       lib::llvm::IntEQ,
1346                                       val,
1347                                       C_bool(false));
1348                     Select(bcx, llcond, C_bool(true), C_bool(false))
1349                 }
1350                 _ => Not(bcx, val)
1351             };
1352             immediate_rvalue_bcx(bcx, llresult, un_ty)
1353         }
1354         ast::neg => {
1355             let Result {bcx, val} = trans_to_datum(bcx, sub_expr).to_result();
1356             let llneg = {
1357                 if ty::type_is_fp(un_ty) {
1358                     FNeg(bcx, val)
1359                 } else {
1360                     Neg(bcx, val)
1361                 }
1362             };
1363             immediate_rvalue_bcx(bcx, llneg, un_ty)
1364         }
1365         ast::box(_) => {
1366             trans_boxed_expr(bcx, un_ty, sub_expr, sub_ty,
1367                              heap_managed)
1368         }
1369         ast::uniq => {
1370             let heap  = heap_for_unique(bcx, un_ty);
1371             trans_boxed_expr(bcx, un_ty, sub_expr, sub_ty, heap)
1372         }
1373         ast::deref => {
1374             bcx.sess().bug("deref expressions should have been \
1375                             translated using trans_lvalue(), not \
1376                             trans_unary_datum()")
1377         }
1378     };
1379
1380     fn trans_boxed_expr(bcx: @mut Block,
1381                         box_ty: ty::t,
1382                         contents: @ast::expr,
1383                         contents_ty: ty::t,
1384                         heap: heap) -> DatumBlock {
1385         let _icx = push_ctxt("trans_boxed_expr");
1386         if heap == heap_exchange {
1387             let llty = type_of(bcx.ccx(), contents_ty);
1388             let size = llsize_of(bcx.ccx(), llty);
1389             let Result { bcx: bcx, val: val } = malloc_raw_dyn(bcx, contents_ty,
1390                                                                heap_exchange, size);
1391             add_clean_free(bcx, val, heap_exchange);
1392             let bcx = trans_into(bcx, contents, SaveIn(val));
1393             revoke_clean(bcx, val);
1394             return immediate_rvalue_bcx(bcx, val, box_ty);
1395         } else {
1396             let base::MallocResult { bcx, box: bx, body } =
1397                 base::malloc_general(bcx, contents_ty, heap);
1398             add_clean_free(bcx, bx, heap);
1399             let bcx = trans_into(bcx, contents, SaveIn(body));
1400             revoke_clean(bcx, bx);
1401             return immediate_rvalue_bcx(bcx, bx, box_ty);
1402         }
1403     }
1404 }
1405
1406 fn trans_addr_of(bcx: @mut Block, expr: &ast::expr,
1407                  subexpr: @ast::expr) -> DatumBlock {
1408     let _icx = push_ctxt("trans_addr_of");
1409     let mut bcx = bcx;
1410     let sub_datum = unpack_datum!(bcx, trans_to_datum(bcx, subexpr));
1411     let llval = sub_datum.to_ref_llval(bcx);
1412     return immediate_rvalue_bcx(bcx, llval, expr_ty(bcx, expr));
1413 }
1414
1415 // Important to get types for both lhs and rhs, because one might be _|_
1416 // and the other not.
1417 fn trans_eager_binop(bcx: @mut Block,
1418                      binop_expr: &ast::expr,
1419                      binop_ty: ty::t,
1420                      op: ast::binop,
1421                      lhs_datum: &Datum,
1422                      rhs_datum: &Datum)
1423                   -> DatumBlock {
1424     let _icx = push_ctxt("trans_eager_binop");
1425
1426     let lhs = lhs_datum.to_appropriate_llval(bcx);
1427     let lhs_t = lhs_datum.ty;
1428
1429     let rhs = rhs_datum.to_appropriate_llval(bcx);
1430     let rhs_t = rhs_datum.ty;
1431
1432     let mut intype = {
1433         if ty::type_is_bot(lhs_t) { rhs_t }
1434         else { lhs_t }
1435     };
1436     let tcx = bcx.tcx();
1437     if ty::type_is_simd(tcx, intype) {
1438         intype = ty::simd_type(tcx, intype);
1439     }
1440     let is_float = ty::type_is_fp(intype);
1441     let signed = ty::type_is_signed(intype);
1442
1443     let rhs = base::cast_shift_expr_rhs(bcx, op, lhs, rhs);
1444
1445     let mut bcx = bcx;
1446     let val = match op {
1447       ast::add => {
1448         if is_float { FAdd(bcx, lhs, rhs) }
1449         else { Add(bcx, lhs, rhs) }
1450       }
1451       ast::subtract => {
1452         if is_float { FSub(bcx, lhs, rhs) }
1453         else { Sub(bcx, lhs, rhs) }
1454       }
1455       ast::mul => {
1456         if is_float { FMul(bcx, lhs, rhs) }
1457         else { Mul(bcx, lhs, rhs) }
1458       }
1459       ast::div => {
1460         if is_float {
1461             FDiv(bcx, lhs, rhs)
1462         } else {
1463             // Only zero-check integers; fp /0 is NaN
1464             bcx = base::fail_if_zero(bcx, binop_expr.span,
1465                                      op, rhs, rhs_t);
1466             if signed {
1467                 SDiv(bcx, lhs, rhs)
1468             } else {
1469                 UDiv(bcx, lhs, rhs)
1470             }
1471         }
1472       }
1473       ast::rem => {
1474         if is_float {
1475             FRem(bcx, lhs, rhs)
1476         } else {
1477             // Only zero-check integers; fp %0 is NaN
1478             bcx = base::fail_if_zero(bcx, binop_expr.span,
1479                                      op, rhs, rhs_t);
1480             if signed {
1481                 SRem(bcx, lhs, rhs)
1482             } else {
1483                 URem(bcx, lhs, rhs)
1484             }
1485         }
1486       }
1487       ast::bitor => Or(bcx, lhs, rhs),
1488       ast::bitand => And(bcx, lhs, rhs),
1489       ast::bitxor => Xor(bcx, lhs, rhs),
1490       ast::shl => Shl(bcx, lhs, rhs),
1491       ast::shr => {
1492         if signed {
1493             AShr(bcx, lhs, rhs)
1494         } else { LShr(bcx, lhs, rhs) }
1495       }
1496       ast::eq | ast::ne | ast::lt | ast::ge | ast::le | ast::gt => {
1497         if ty::type_is_bot(rhs_t) {
1498             C_bool(false)
1499         } else {
1500             if !ty::type_is_scalar(rhs_t) {
1501                 bcx.tcx().sess.span_bug(binop_expr.span,
1502                                         "non-scalar comparison");
1503             }
1504             let cmpr = base::compare_scalar_types(bcx, lhs, rhs, rhs_t, op);
1505             bcx = cmpr.bcx;
1506             ZExt(bcx, cmpr.val, Type::i8())
1507         }
1508       }
1509       _ => {
1510         bcx.tcx().sess.span_bug(binop_expr.span, "unexpected binop");
1511       }
1512     };
1513
1514     return immediate_rvalue_bcx(bcx, val, binop_ty);
1515 }
1516
1517 // refinement types would obviate the need for this
1518 enum lazy_binop_ty { lazy_and, lazy_or }
1519
1520 fn trans_lazy_binop(bcx: @mut Block,
1521                     binop_expr: &ast::expr,
1522                     op: lazy_binop_ty,
1523                     a: @ast::expr,
1524                     b: @ast::expr) -> DatumBlock {
1525     let _icx = push_ctxt("trans_lazy_binop");
1526     let binop_ty = expr_ty(bcx, binop_expr);
1527     let bcx = bcx;
1528
1529     let Result {bcx: past_lhs, val: lhs} = {
1530         do base::with_scope_result(bcx, a.info(), "lhs") |bcx| {
1531             trans_to_datum(bcx, a).to_result()
1532         }
1533     };
1534
1535     if past_lhs.unreachable {
1536         return immediate_rvalue_bcx(past_lhs, lhs, binop_ty);
1537     }
1538
1539     let join = base::sub_block(bcx, "join");
1540     let before_rhs = base::sub_block(bcx, "rhs");
1541
1542     let lhs_i1 = bool_to_i1(past_lhs, lhs);
1543     match op {
1544       lazy_and => CondBr(past_lhs, lhs_i1, before_rhs.llbb, join.llbb),
1545       lazy_or => CondBr(past_lhs, lhs_i1, join.llbb, before_rhs.llbb)
1546     }
1547
1548     let Result {bcx: past_rhs, val: rhs} = {
1549         do base::with_scope_result(before_rhs, b.info(), "rhs") |bcx| {
1550             trans_to_datum(bcx, b).to_result()
1551         }
1552     };
1553
1554     if past_rhs.unreachable {
1555         return immediate_rvalue_bcx(join, lhs, binop_ty);
1556     }
1557
1558     Br(past_rhs, join.llbb);
1559     let phi = Phi(join, Type::bool(), [lhs, rhs], [past_lhs.llbb,
1560                                                past_rhs.llbb]);
1561
1562     return immediate_rvalue_bcx(join, phi, binop_ty);
1563 }
1564
1565 fn trans_binary(bcx: @mut Block,
1566                 binop_expr: &ast::expr,
1567                 op: ast::binop,
1568                 lhs: @ast::expr,
1569                 rhs: @ast::expr) -> DatumBlock
1570 {
1571     let _icx = push_ctxt("trans_binary");
1572
1573     match op {
1574         ast::and => {
1575             trans_lazy_binop(bcx, binop_expr, lazy_and, lhs, rhs)
1576         }
1577         ast::or => {
1578             trans_lazy_binop(bcx, binop_expr, lazy_or, lhs, rhs)
1579         }
1580         _ => {
1581             let mut bcx = bcx;
1582             let lhs_datum = unpack_datum!(bcx, trans_to_datum(bcx, lhs));
1583             let rhs_datum = unpack_datum!(bcx, trans_to_datum(bcx, rhs));
1584             let binop_ty = expr_ty(bcx, binop_expr);
1585             trans_eager_binop(bcx, binop_expr, binop_ty, op,
1586                               &lhs_datum, &rhs_datum)
1587         }
1588     }
1589 }
1590
1591 fn trans_overloaded_op(bcx: @mut Block,
1592                        expr: &ast::expr,
1593                        callee_id: ast::NodeId,
1594                        rcvr: @ast::expr,
1595                        args: ~[@ast::expr],
1596                        ret_ty: ty::t,
1597                        dest: Dest)
1598                        -> @mut Block {
1599     let origin = bcx.ccx().maps.method_map.get_copy(&expr.id);
1600     let fty = node_id_type(bcx, callee_id);
1601     callee::trans_call_inner(bcx,
1602                              expr.info(),
1603                              fty,
1604                              ret_ty,
1605                              |bcx| {
1606                                 meth::trans_method_callee(bcx,
1607                                                           callee_id,
1608                                                           rcvr,
1609                                                           origin)
1610                              },
1611                              callee::ArgExprs(args),
1612                              Some(dest),
1613                              DoAutorefArg).bcx
1614 }
1615
1616 fn int_cast(bcx: @mut Block, lldsttype: Type, llsrctype: Type,
1617             llsrc: ValueRef, signed: bool) -> ValueRef {
1618     let _icx = push_ctxt("int_cast");
1619     unsafe {
1620         let srcsz = llvm::LLVMGetIntTypeWidth(llsrctype.to_ref());
1621         let dstsz = llvm::LLVMGetIntTypeWidth(lldsttype.to_ref());
1622         return if dstsz == srcsz {
1623             BitCast(bcx, llsrc, lldsttype)
1624         } else if srcsz > dstsz {
1625             TruncOrBitCast(bcx, llsrc, lldsttype)
1626         } else if signed {
1627             SExtOrBitCast(bcx, llsrc, lldsttype)
1628         } else {
1629             ZExtOrBitCast(bcx, llsrc, lldsttype)
1630         };
1631     }
1632 }
1633
1634 fn float_cast(bcx: @mut Block, lldsttype: Type, llsrctype: Type,
1635               llsrc: ValueRef) -> ValueRef {
1636     let _icx = push_ctxt("float_cast");
1637     let srcsz = llsrctype.float_width();
1638     let dstsz = lldsttype.float_width();
1639     return if dstsz > srcsz {
1640         FPExt(bcx, llsrc, lldsttype)
1641     } else if srcsz > dstsz {
1642         FPTrunc(bcx, llsrc, lldsttype)
1643     } else { llsrc };
1644 }
1645
1646 #[deriving(Eq)]
1647 pub enum cast_kind {
1648     cast_pointer,
1649     cast_integral,
1650     cast_float,
1651     cast_enum,
1652     cast_other,
1653 }
1654
1655 pub fn cast_type_kind(t: ty::t) -> cast_kind {
1656     match ty::get(t).sty {
1657         ty::ty_float(*)   => cast_float,
1658         ty::ty_ptr(*)     => cast_pointer,
1659         ty::ty_rptr(*)    => cast_pointer,
1660         ty::ty_int(*)     => cast_integral,
1661         ty::ty_uint(*)    => cast_integral,
1662         ty::ty_bool       => cast_integral,
1663         ty::ty_enum(*)    => cast_enum,
1664         _                 => cast_other
1665     }
1666 }
1667
1668 fn trans_imm_cast(bcx: @mut Block, expr: @ast::expr,
1669                   id: ast::NodeId) -> DatumBlock {
1670     let _icx = push_ctxt("trans_cast");
1671     let ccx = bcx.ccx();
1672
1673     let t_out = node_id_type(bcx, id);
1674
1675     let mut bcx = bcx;
1676     let llexpr = unpack_result!(bcx, trans_to_datum(bcx, expr).to_result());
1677     let ll_t_in = val_ty(llexpr);
1678     let t_in = expr_ty(bcx, expr);
1679     let ll_t_out = type_of::type_of(ccx, t_out);
1680
1681     let k_in = cast_type_kind(t_in);
1682     let k_out = cast_type_kind(t_out);
1683     let s_in = k_in == cast_integral && ty::type_is_signed(t_in);
1684
1685     let newval =
1686         match (k_in, k_out) {
1687             (cast_integral, cast_integral) => {
1688                 int_cast(bcx, ll_t_out, ll_t_in, llexpr, s_in)
1689             }
1690             (cast_float, cast_float) => {
1691                 float_cast(bcx, ll_t_out, ll_t_in, llexpr)
1692             }
1693             (cast_integral, cast_float) => {
1694                 if s_in {
1695                     SIToFP(bcx, llexpr, ll_t_out)
1696                 } else { UIToFP(bcx, llexpr, ll_t_out) }
1697             }
1698             (cast_float, cast_integral) => {
1699                 if ty::type_is_signed(t_out) {
1700                     FPToSI(bcx, llexpr, ll_t_out)
1701                 } else { FPToUI(bcx, llexpr, ll_t_out) }
1702             }
1703             (cast_integral, cast_pointer) => {
1704                 IntToPtr(bcx, llexpr, ll_t_out)
1705             }
1706             (cast_pointer, cast_integral) => {
1707                 PtrToInt(bcx, llexpr, ll_t_out)
1708             }
1709             (cast_pointer, cast_pointer) => {
1710                 PointerCast(bcx, llexpr, ll_t_out)
1711             }
1712             (cast_enum, cast_integral) |
1713             (cast_enum, cast_float) => {
1714                 let bcx = bcx;
1715                 let repr = adt::represent_type(ccx, t_in);
1716                 let lldiscrim_a = adt::trans_get_discr(bcx, repr, llexpr);
1717                 match k_out {
1718                     cast_integral => int_cast(bcx, ll_t_out,
1719                                               val_ty(lldiscrim_a),
1720                                               lldiscrim_a, true),
1721                     cast_float => SIToFP(bcx, lldiscrim_a, ll_t_out),
1722                     _ => ccx.sess.bug("translating unsupported cast.")
1723                 }
1724             }
1725             _ => ccx.sess.bug("translating unsupported cast.")
1726         };
1727     return immediate_rvalue_bcx(bcx, newval, t_out);
1728 }
1729
1730 fn trans_assign_op(bcx: @mut Block,
1731                    expr: @ast::expr,
1732                    callee_id: ast::NodeId,
1733                    op: ast::binop,
1734                    dst: @ast::expr,
1735                    src: @ast::expr) -> @mut Block
1736 {
1737     let _icx = push_ctxt("trans_assign_op");
1738     let mut bcx = bcx;
1739
1740     debug!("trans_assign_op(expr=%s)", bcx.expr_to_str(expr));
1741
1742     // Evaluate LHS (destination), which should be an lvalue
1743     let dst_datum = unpack_datum!(bcx, trans_lvalue_unadjusted(bcx, dst));
1744
1745     // A user-defined operator method
1746     if bcx.ccx().maps.method_map.find(&expr.id).is_some() {
1747         // FIXME(#2528) evaluates the receiver twice!!
1748         let scratch = scratch_datum(bcx, dst_datum.ty, "__assign_op", false);
1749         let bcx = trans_overloaded_op(bcx,
1750                                       expr,
1751                                       callee_id,
1752                                       dst,
1753                                       ~[src],
1754                                       dst_datum.ty,
1755                                       SaveIn(scratch.val));
1756         return scratch.move_to_datum(bcx, DROP_EXISTING, dst_datum);
1757     }
1758
1759     // Evaluate RHS (source)
1760     let src_datum = unpack_datum!(bcx, trans_to_datum(bcx, src));
1761
1762     // Perform computation and store the result
1763     let result_datum =
1764         unpack_datum!(bcx,
1765                       trans_eager_binop(
1766                           bcx, expr, dst_datum.ty, op,
1767                           &dst_datum, &src_datum));
1768     return result_datum.copy_to_datum(bcx, DROP_EXISTING, dst_datum);
1769 }
1770
1771 fn shorten(x: &str) -> @str {
1772     (if x.char_len() > 60 {x.slice_chars(0, 60)} else {x}).to_managed()
1773 }