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