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