src/librustc/middle/trans/controlflow.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use llvm::*;
  12 use driver::config::FullDebugInfo;
  13 use middle::def;
  14 use middle::lang_items::{FailFnLangItem, FailBoundsCheckFnLangItem};
  15 use middle::trans::_match;
  16 use middle::trans::adt;
  17 use middle::trans::base::*;
  18 use middle::trans::build::*;
  19 use middle::trans::callee;
  20 use middle::trans::cleanup::CleanupMethods;
  21 use middle::trans::cleanup;
  22 use middle::trans::common::*;
  23 use middle::trans::datum;
  24 use middle::trans::debuginfo;
  25 use middle::trans::expr;
  26 use middle::trans::meth;
  27 use middle::trans::type_::Type;
  28 use middle::ty;
  29 use middle::typeck::MethodCall;
  30 use util::ppaux::Repr;
  31 use util::ppaux;
  32
  33 use syntax::ast;
  34 use syntax::ast::Ident;
  35 use syntax::ast_util;
  36 use syntax::codemap::Span;
  37 use syntax::parse::token::InternedString;
  38 use syntax::parse::token;
  39 use syntax::visit::Visitor;
  40
  41 use std::gc::Gc;
  42
  43 pub fn trans_stmt<'a>(cx: &'a Block<'a>,
  44                       s: &ast::Stmt)
  45                       -> &'a Block<'a> {
  46     let _icx = push_ctxt("trans_stmt");
  47     let fcx = cx.fcx;
  48     debug!("trans_stmt({})", s.repr(cx.tcx()));
  49
  50     if cx.sess().asm_comments() {
  51         add_span_comment(cx, s.span, s.repr(cx.tcx()).as_slice());
  52     }
  53
  54     let mut bcx = cx;
  55
  56     let id = ast_util::stmt_id(s);
  57     fcx.push_ast_cleanup_scope(id);
  58
  59     match s.node {
  60         ast::StmtExpr(ref e, _) | ast::StmtSemi(ref e, _) => {
  61             bcx = trans_stmt_semi(bcx, &**e);
  62         }
  63         ast::StmtDecl(d, _) => {
  64             match d.node {
  65                 ast::DeclLocal(ref local) => {
  66                     bcx = init_local(bcx, &**local);
  67                     if cx.sess().opts.debuginfo == FullDebugInfo {
  68                         debuginfo::create_local_var_metadata(bcx, &**local);
  69                     }
  70                 }
  71                 ast::DeclItem(ref i) => {
  72                     match fcx.handle_items {
  73                         TranslateItems => trans_item(cx.fcx.ccx, &**i),
  74                         IgnoreItems => {}
  75                     }
  76                 }
  77             }
  78         }
  79         ast::StmtMac(..) => cx.tcx().sess.bug("unexpanded macro")
  80     }
  81
  82     bcx = fcx.pop_and_trans_ast_cleanup_scope(
  83         bcx, ast_util::stmt_id(s));
  84
  85     return bcx;
  86 }
  87
  88 pub fn trans_stmt_semi<'a>(cx: &'a Block<'a>, e: &ast::Expr) -> &'a Block<'a> {
  89     let _icx = push_ctxt("trans_stmt_semi");
  90     let ty = expr_ty(cx, e);
  91     if ty::type_needs_drop(cx.tcx(), ty) {
  92         expr::trans_to_lvalue(cx, e, "stmt").bcx
  93     } else {
  94         expr::trans_into(cx, e, expr::Ignore)
  95     }
  96 }
  97
  98 pub fn trans_block<'a>(bcx: &'a Block<'a>,
  99                        b: &ast::Block,
 100                        mut dest: expr::Dest)
 101                        -> &'a Block<'a> {
 102     let _icx = push_ctxt("trans_block");
 103     let fcx = bcx.fcx;
 104     let mut bcx = bcx;
 105
 106     fcx.push_ast_cleanup_scope(b.id);
 107
 108     for s in b.stmts.iter() {
 109         bcx = trans_stmt(bcx, &**s);
 110     }
 111
 112     if dest != expr::Ignore {
 113         let block_ty = node_id_type(bcx, b.id);
 114         if b.expr.is_none() || type_is_zero_size(bcx.ccx(), block_ty) {
 115             dest = expr::Ignore;
 116         }
 117     }
 118
 119     match b.expr {
 120         Some(ref e) => {
 121             bcx = expr::trans_into(bcx, &**e, dest);
 122         }
 123         None => {
 124             assert!(dest == expr::Ignore || bcx.unreachable.get());
 125         }
 126     }
 127
 128     bcx = fcx.pop_and_trans_ast_cleanup_scope(bcx, b.id);
 129
 130     return bcx;
 131 }
 132
 133 pub fn trans_if<'a>(bcx: &'a Block<'a>,
 134                     if_id: ast::NodeId,
 135                     cond: &ast::Expr,
 136                     thn: ast::P<ast::Block>,
 137                     els: Option<Gc<ast::Expr>>,
 138                     dest: expr::Dest)
 139                     -> &'a Block<'a> {
 140     debug!("trans_if(bcx={}, if_id={}, cond={}, thn={:?}, dest={})",
 141            bcx.to_str(), if_id, bcx.expr_to_string(cond), thn.id,
 142            dest.to_string(bcx.ccx()));
 143     let _icx = push_ctxt("trans_if");
 144     let mut bcx = bcx;
 145
 146     let cond_val = unpack_result!(bcx, expr::trans(bcx, cond).to_llbool());
 147
 148     // Drop branches that are known to be impossible
 149     if is_const(cond_val) && !is_undef(cond_val) {
 150         if const_to_uint(cond_val) == 1 {
 151             match els {
 152                 Some(elexpr) => {
 153                     let mut trans = TransItemVisitor { ccx: bcx.fcx.ccx };
 154                     trans.visit_expr(&*elexpr, ());
 155                 }
 156                 None => {}
 157             }
 158             // if true { .. } [else { .. }]
 159             bcx = trans_block(bcx, &*thn, dest);
 160             debuginfo::clear_source_location(bcx.fcx);
 161         } else {
 162             let mut trans = TransItemVisitor { ccx: bcx.fcx.ccx } ;
 163             trans.visit_block(&*thn, ());
 164
 165             match els {
 166                 // if false { .. } else { .. }
 167                 Some(elexpr) => {
 168                     bcx = expr::trans_into(bcx, &*elexpr, dest);
 169                     debuginfo::clear_source_location(bcx.fcx);
 170                 }
 171
 172                 // if false { .. }
 173                 None => { }
 174             }
 175         }
 176
 177         return bcx;
 178     }
 179
 180     let name = format!("then-block-{}-", thn.id);
 181     let then_bcx_in = bcx.fcx.new_id_block(name.as_slice(), thn.id);
 182     let then_bcx_out = trans_block(then_bcx_in, &*thn, dest);
 183     debuginfo::clear_source_location(bcx.fcx);
 184
 185     let next_bcx;
 186     match els {
 187         Some(elexpr) => {
 188             let else_bcx_in = bcx.fcx.new_id_block("else-block", elexpr.id);
 189             let else_bcx_out = expr::trans_into(else_bcx_in, &*elexpr, dest);
 190             next_bcx = bcx.fcx.join_blocks(if_id,
 191                                            [then_bcx_out, else_bcx_out]);
 192             CondBr(bcx, cond_val, then_bcx_in.llbb, else_bcx_in.llbb);
 193         }
 194
 195         None => {
 196             next_bcx = bcx.fcx.new_id_block("next-block", if_id);
 197             Br(then_bcx_out, next_bcx.llbb);
 198             CondBr(bcx, cond_val, then_bcx_in.llbb, next_bcx.llbb);
 199         }
 200     }
 201
 202     // Clear the source location because it is still set to whatever has been translated
 203     // right before.
 204     debuginfo::clear_source_location(next_bcx.fcx);
 205
 206     next_bcx
 207 }
 208
 209 pub fn trans_while<'a>(bcx: &'a Block<'a>,
 210                        loop_id: ast::NodeId,
 211                        cond: &ast::Expr,
 212                        body: &ast::Block)
 213                        -> &'a Block<'a> {
 214     let _icx = push_ctxt("trans_while");
 215     let fcx = bcx.fcx;
 216
 217     //            bcx
 218     //             |
 219     //         cond_bcx_in  <--------+
 220     //             |                 |
 221     //         cond_bcx_out          |
 222     //           |      |            |
 223     //           |    body_bcx_in    |
 224     // cleanup_blk      |            |
 225     //    |           body_bcx_out --+
 226     // next_bcx_in
 227
 228     let next_bcx_in = fcx.new_id_block("while_exit", loop_id);
 229     let cond_bcx_in = fcx.new_id_block("while_cond", cond.id);
 230     let body_bcx_in = fcx.new_id_block("while_body", body.id);
 231
 232     fcx.push_loop_cleanup_scope(loop_id, [next_bcx_in, cond_bcx_in]);
 233
 234     Br(bcx, cond_bcx_in.llbb);
 235
 236     // compile the block where we will handle loop cleanups
 237     let cleanup_llbb = fcx.normal_exit_block(loop_id, cleanup::EXIT_BREAK);
 238
 239     // compile the condition
 240     let Result {bcx: cond_bcx_out, val: cond_val} =
 241         expr::trans(cond_bcx_in, cond).to_llbool();
 242     CondBr(cond_bcx_out, cond_val, body_bcx_in.llbb, cleanup_llbb);
 243
 244     // loop body:
 245     let body_bcx_out = trans_block(body_bcx_in, body, expr::Ignore);
 246     Br(body_bcx_out, cond_bcx_in.llbb);
 247
 248     fcx.pop_loop_cleanup_scope(loop_id);
 249     return next_bcx_in;
 250 }
 251
 252 /// Translates a `for` loop.
 253 pub fn trans_for<'a>(
 254                  mut bcx: &'a Block<'a>,
 255                  loop_info: NodeInfo,
 256                  pat: Gc<ast::Pat>,
 257                  head: &ast::Expr,
 258                  body: &ast::Block)
 259                  -> &'a Block<'a> {
 260     let _icx = push_ctxt("trans_for");
 261
 262     //            bcx
 263     //             |
 264     //      loopback_bcx_in  <-------+
 265     //             |                 |
 266     //      loopback_bcx_out         |
 267     //           |      |            |
 268     //           |    body_bcx_in    |
 269     // cleanup_blk      |            |
 270     //    |           body_bcx_out --+
 271     // next_bcx_in
 272
 273     // Codegen the head to create the iterator value.
 274     let iterator_datum =
 275         unpack_datum!(bcx, expr::trans_to_lvalue(bcx, head, "for_head"));
 276     let iterator_type = node_id_type(bcx, head.id);
 277     debug!("iterator type is {}, datum type is {}",
 278            ppaux::ty_to_string(bcx.tcx(), iterator_type),
 279            ppaux::ty_to_string(bcx.tcx(), iterator_datum.ty));
 280     let lliterator = load_ty(bcx, iterator_datum.val, iterator_datum.ty);
 281
 282     // Create our basic blocks and set up our loop cleanups.
 283     let next_bcx_in = bcx.fcx.new_id_block("for_exit", loop_info.id);
 284     let loopback_bcx_in = bcx.fcx.new_id_block("for_loopback", head.id);
 285     let body_bcx_in = bcx.fcx.new_id_block("for_body", body.id);
 286     bcx.fcx.push_loop_cleanup_scope(loop_info.id,
 287                                     [next_bcx_in, loopback_bcx_in]);
 288     Br(bcx, loopback_bcx_in.llbb);
 289     let cleanup_llbb = bcx.fcx.normal_exit_block(loop_info.id,
 290                                                  cleanup::EXIT_BREAK);
 291
 292     // Set up the method call (to `.next()`).
 293     let method_call = MethodCall::expr(loop_info.id);
 294     let method_type = loopback_bcx_in.tcx()
 295                                      .method_map
 296                                      .borrow()
 297                                      .get(&method_call)
 298                                      .ty;
 299     let method_type = monomorphize_type(loopback_bcx_in, method_type);
 300     let method_result_type = ty::ty_fn_ret(method_type);
 301     let option_cleanup_scope = body_bcx_in.fcx.push_custom_cleanup_scope();
 302     let option_cleanup_scope_id = cleanup::CustomScope(option_cleanup_scope);
 303
 304     // Compile the method call (to `.next()`).
 305     let mut loopback_bcx_out = loopback_bcx_in;
 306     let option_datum =
 307         unpack_datum!(loopback_bcx_out,
 308                       datum::lvalue_scratch_datum(loopback_bcx_out,
 309                                                   method_result_type,
 310                                                   "loop_option",
 311                                                   false,
 312                                                   option_cleanup_scope_id,
 313                                                   (),
 314                                                   |(), bcx, lloption| {
 315         let Result {
 316             bcx: bcx,
 317             val: _
 318         } = callee::trans_call_inner(bcx,
 319                                      Some(loop_info),
 320                                      method_type,
 321                                      |bcx, arg_cleanup_scope| {
 322                                          meth::trans_method_callee(
 323                                              bcx,
 324                                              method_call,
 325                                              None,
 326                                              arg_cleanup_scope)
 327                                      },
 328                                      callee::ArgVals([lliterator]),
 329                                      Some(expr::SaveIn(lloption)));
 330         bcx
 331     }));
 332
 333     // Check the discriminant; if the `None` case, exit the loop.
 334     let option_representation = adt::represent_type(loopback_bcx_out.ccx(),
 335                                                     method_result_type);
 336     let i8_type = Type::i8(loopback_bcx_out.ccx());
 337     let lldiscriminant = adt::trans_get_discr(loopback_bcx_out,
 338                                               &*option_representation,
 339                                               option_datum.val,
 340                                               Some(i8_type));
 341     let llzero = C_u8(loopback_bcx_out.ccx(), 0);
 342     let llcondition = ICmp(loopback_bcx_out, IntNE, lldiscriminant, llzero);
 343     CondBr(loopback_bcx_out, llcondition, body_bcx_in.llbb, cleanup_llbb);
 344
 345     // Now we're in the body. Unpack the `Option` value into the programmer-
 346     // supplied pattern.
 347     let llpayload = adt::trans_field_ptr(body_bcx_in,
 348                                          &*option_representation,
 349                                          option_datum.val,
 350                                          1,
 351                                          0);
 352     let binding_cleanup_scope = body_bcx_in.fcx.push_custom_cleanup_scope();
 353     let binding_cleanup_scope_id =
 354         cleanup::CustomScope(binding_cleanup_scope);
 355     let mut body_bcx_out =
 356         _match::store_for_loop_binding(body_bcx_in,
 357                                        pat,
 358                                        llpayload,
 359                                        binding_cleanup_scope_id);
 360
 361     // Codegen the body.
 362     body_bcx_out = trans_block(body_bcx_out, body, expr::Ignore);
 363     body_bcx_out.fcx.pop_custom_cleanup_scope(binding_cleanup_scope);
 364     body_bcx_out =
 365         body_bcx_out.fcx
 366                     .pop_and_trans_custom_cleanup_scope(body_bcx_out,
 367                                                         option_cleanup_scope);
 368     Br(body_bcx_out, loopback_bcx_in.llbb);
 369
 370     // Codegen cleanups and leave.
 371     next_bcx_in.fcx.pop_loop_cleanup_scope(loop_info.id);
 372     next_bcx_in
 373 }
 374
 375 pub fn trans_loop<'a>(bcx:&'a Block<'a>,
 376                       loop_id: ast::NodeId,
 377                       body: &ast::Block)
 378                       -> &'a Block<'a> {
 379     let _icx = push_ctxt("trans_loop");
 380     let fcx = bcx.fcx;
 381
 382     //            bcx
 383     //             |
 384     //         body_bcx_in
 385     //             |
 386     //         body_bcx_out
 387     //
 388     // next_bcx
 389     //
 390     // Links between body_bcx_in and next_bcx are created by
 391     // break statements.
 392
 393     let next_bcx_in = bcx.fcx.new_id_block("loop_exit", loop_id);
 394     let body_bcx_in = bcx.fcx.new_id_block("loop_body", body.id);
 395
 396     fcx.push_loop_cleanup_scope(loop_id, [next_bcx_in, body_bcx_in]);
 397
 398     Br(bcx, body_bcx_in.llbb);
 399     let body_bcx_out = trans_block(body_bcx_in, body, expr::Ignore);
 400     Br(body_bcx_out, body_bcx_in.llbb);
 401
 402     fcx.pop_loop_cleanup_scope(loop_id);
 403
 404     if ty::type_is_bot(node_id_type(bcx, loop_id)) {
 405         Unreachable(next_bcx_in);
 406     }
 407
 408     return next_bcx_in;
 409 }
 410
 411 pub fn trans_break_cont<'a>(bcx: &'a Block<'a>,
 412                             expr_id: ast::NodeId,
 413                             opt_label: Option<Ident>,
 414                             exit: uint)
 415                             -> &'a Block<'a> {
 416     let _icx = push_ctxt("trans_break_cont");
 417     let fcx = bcx.fcx;
 418
 419     if bcx.unreachable.get() {
 420         return bcx;
 421     }
 422
 423     // Locate loop that we will break to
 424     let loop_id = match opt_label {
 425         None => fcx.top_loop_scope(),
 426         Some(_) => {
 427             match bcx.tcx().def_map.borrow().find(&expr_id) {
 428                 Some(&def::DefLabel(loop_id)) => loop_id,
 429                 ref r => {
 430                     bcx.tcx().sess.bug(format!("{:?} in def-map for label",
 431                                                r).as_slice())
 432                 }
 433             }
 434         }
 435     };
 436
 437     // Generate appropriate cleanup code and branch
 438     let cleanup_llbb = fcx.normal_exit_block(loop_id, exit);
 439     Br(bcx, cleanup_llbb);
 440     Unreachable(bcx); // anything afterwards should be ignored
 441     return bcx;
 442 }
 443
 444 pub fn trans_break<'a>(bcx: &'a Block<'a>,
 445                        expr_id: ast::NodeId,
 446                        label_opt: Option<Ident>)
 447                        -> &'a Block<'a> {
 448     return trans_break_cont(bcx, expr_id, label_opt, cleanup::EXIT_BREAK);
 449 }
 450
 451 pub fn trans_cont<'a>(bcx: &'a Block<'a>,
 452                       expr_id: ast::NodeId,
 453                       label_opt: Option<Ident>)
 454                       -> &'a Block<'a> {
 455     return trans_break_cont(bcx, expr_id, label_opt, cleanup::EXIT_LOOP);
 456 }
 457
 458 pub fn trans_ret<'a>(bcx: &'a Block<'a>,
 459                      e: Option<Gc<ast::Expr>>)
 460                      -> &'a Block<'a> {
 461     let _icx = push_ctxt("trans_ret");
 462     let fcx = bcx.fcx;
 463     let mut bcx = bcx;
 464     let dest = match bcx.fcx.llretptr.get() {
 465         None => expr::Ignore,
 466         Some(retptr) => expr::SaveIn(retptr),
 467     };
 468     match e {
 469         Some(x) => {
 470             bcx = expr::trans_into(bcx, &*x, dest);
 471         }
 472         _ => {}
 473     }
 474     let cleanup_llbb = fcx.return_exit_block();
 475     Br(bcx, cleanup_llbb);
 476     Unreachable(bcx);
 477     return bcx;
 478 }
 479
 480 fn str_slice_arg<'a>(bcx: &'a Block<'a>, s: InternedString) -> ValueRef {
 481     let ccx = bcx.ccx();
 482     let s = C_str_slice(ccx, s);
 483     let slot = alloca(bcx, val_ty(s), "__temp");
 484     Store(bcx, s, slot);
 485     slot
 486 }
 487
 488 pub fn trans_fail<'a>(
 489                   bcx: &'a Block<'a>,
 490                   sp: Span,
 491                   fail_str: InternedString)
 492                   -> &'a Block<'a> {
 493     let ccx = bcx.ccx();
 494     let _icx = push_ctxt("trans_fail_value");
 495
 496     let v_str = str_slice_arg(bcx, fail_str);
 497     let loc = bcx.sess().codemap().lookup_char_pos(sp.lo);
 498     let filename = token::intern_and_get_ident(loc.file.name.as_slice());
 499     let v_filename = str_slice_arg(bcx, filename);
 500     let v_line = loc.line as int;
 501     let args = vec!(v_str, v_filename, C_int(ccx, v_line));
 502     let did = langcall(bcx, Some(sp), "", FailFnLangItem);
 503     let bcx = callee::trans_lang_call(bcx,
 504                                       did,
 505                                       args.as_slice(),
 506                                       Some(expr::Ignore)).bcx;
 507     Unreachable(bcx);
 508     return bcx;
 509 }
 510
 511 pub fn trans_fail_bounds_check<'a>(
 512                                bcx: &'a Block<'a>,
 513                                sp: Span,
 514                                index: ValueRef,
 515                                len: ValueRef)
 516                                -> &'a Block<'a> {
 517     let _icx = push_ctxt("trans_fail_bounds_check");
 518
 519     // Extract the file/line from the span
 520     let loc = bcx.sess().codemap().lookup_char_pos(sp.lo);
 521     let filename = token::intern_and_get_ident(loc.file.name.as_slice());
 522
 523     // Invoke the lang item
 524     let filename = str_slice_arg(bcx, filename);
 525     let line = C_int(bcx.ccx(), loc.line as int);
 526     let args = vec!(filename, line, index, len);
 527     let did = langcall(bcx, Some(sp), "", FailBoundsCheckFnLangItem);
 528     let bcx = callee::trans_lang_call(bcx,
 529                                       did,
 530                                       args.as_slice(),
 531                                       Some(expr::Ignore)).bcx;
 532     Unreachable(bcx);
 533     return bcx;
 534 }