src/librustc_trans/trans/cleanup.rs

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! ## The Cleanup module
  12 //!
  13 //! The cleanup module tracks what values need to be cleaned up as scopes
  14 //! are exited, either via panic or just normal control flow. The basic
  15 //! idea is that the function context maintains a stack of cleanup scopes
  16 //! that are pushed/popped as we traverse the AST tree. There is typically
  17 //! at least one cleanup scope per AST node; some AST nodes may introduce
  18 //! additional temporary scopes.
  19 //!
  20 //! Cleanup items can be scheduled into any of the scopes on the stack.
  21 //! Typically, when a scope is popped, we will also generate the code for
  22 //! each of its cleanups at that time. This corresponds to a normal exit
  23 //! from a block (for example, an expression completing evaluation
  24 //! successfully without panic). However, it is also possible to pop a
  25 //! block *without* executing its cleanups; this is typically used to
  26 //! guard intermediate values that must be cleaned up on panic, but not
  27 //! if everything goes right. See the section on custom scopes below for
  28 //! more details.
  29 //!
  30 //! Cleanup scopes come in three kinds:
  31 //!
  32 //! - **AST scopes:** each AST node in a function body has a corresponding
  33 //!   AST scope. We push the AST scope when we start generate code for an AST
  34 //!   node and pop it once the AST node has been fully generated.
  35 //! - **Loop scopes:** loops have an additional cleanup scope. Cleanups are
  36 //!   never scheduled into loop scopes; instead, they are used to record the
  37 //!   basic blocks that we should branch to when a `continue` or `break` statement
  38 //!   is encountered.
  39 //! - **Custom scopes:** custom scopes are typically used to ensure cleanup
  40 //!   of intermediate values.
  41 //!
  42 //! ### When to schedule cleanup
  43 //!
  44 //! Although the cleanup system is intended to *feel* fairly declarative,
  45 //! it's still important to time calls to `schedule_clean()` correctly.
  46 //! Basically, you should not schedule cleanup for memory until it has
  47 //! been initialized, because if an unwind should occur before the memory
  48 //! is fully initialized, then the cleanup will run and try to free or
  49 //! drop uninitialized memory. If the initialization itself produces
  50 //! byproducts that need to be freed, then you should use temporary custom
  51 //! scopes to ensure that those byproducts will get freed on unwind.  For
  52 //! example, an expression like `box foo()` will first allocate a box in the
  53 //! heap and then call `foo()` -- if `foo()` should panic, this box needs
  54 //! to be *shallowly* freed.
  55 //!
  56 //! ### Long-distance jumps
  57 //!
  58 //! In addition to popping a scope, which corresponds to normal control
  59 //! flow exiting the scope, we may also *jump out* of a scope into some
  60 //! earlier scope on the stack. This can occur in response to a `return`,
  61 //! `break`, or `continue` statement, but also in response to panic. In
  62 //! any of these cases, we will generate a series of cleanup blocks for
  63 //! each of the scopes that is exited. So, if the stack contains scopes A
  64 //! ... Z, and we break out of a loop whose corresponding cleanup scope is
  65 //! X, we would generate cleanup blocks for the cleanups in X, Y, and Z.
  66 //! After cleanup is done we would branch to the exit point for scope X.
  67 //! But if panic should occur, we would generate cleanups for all the
  68 //! scopes from A to Z and then resume the unwind process afterwards.
  69 //!
  70 //! To avoid generating tons of code, we cache the cleanup blocks that we
  71 //! create for breaks, returns, unwinds, and other jumps. Whenever a new
  72 //! cleanup is scheduled, though, we must clear these cached blocks. A
  73 //! possible improvement would be to keep the cached blocks but simply
  74 //! generate a new block which performs the additional cleanup and then
  75 //! branches to the existing cached blocks.
  76 //!
  77 //! ### AST and loop cleanup scopes
  78 //!
  79 //! AST cleanup scopes are pushed when we begin and end processing an AST
  80 //! node. They are used to house cleanups related to rvalue temporary that
  81 //! get referenced (e.g., due to an expression like `&Foo()`). Whenever an
  82 //! AST scope is popped, we always trans all the cleanups, adding the cleanup
  83 //! code after the postdominator of the AST node.
  84 //!
  85 //! AST nodes that represent breakable loops also push a loop scope; the
  86 //! loop scope never has any actual cleanups, it's just used to point to
  87 //! the basic blocks where control should flow after a "continue" or
  88 //! "break" statement. Popping a loop scope never generates code.
  89 //!
  90 //! ### Custom cleanup scopes
  91 //!
  92 //! Custom cleanup scopes are used for a variety of purposes. The most
  93 //! common though is to handle temporary byproducts, where cleanup only
  94 //! needs to occur on panic. The general strategy is to push a custom
  95 //! cleanup scope, schedule *shallow* cleanups into the custom scope, and
  96 //! then pop the custom scope (without transing the cleanups) when
  97 //! execution succeeds normally. This way the cleanups are only trans'd on
  98 //! unwind, and only up until the point where execution succeeded, at
  99 //! which time the complete value should be stored in an lvalue or some
 100 //! other place where normal cleanup applies.
 101 //!
 102 //! To spell it out, here is an example. Imagine an expression `box expr`.
 103 //! We would basically:
 104 //!
 105 //! 1. Push a custom cleanup scope C.
 106 //! 2. Allocate the box.
 107 //! 3. Schedule a shallow free in the scope C.
 108 //! 4. Trans `expr` into the box.
 109 //! 5. Pop the scope C.
 110 //! 6. Return the box as an rvalue.
 111 //!
 112 //! This way, if a panic occurs while transing `expr`, the custom
 113 //! cleanup scope C is pushed and hence the box will be freed. The trans
 114 //! code for `expr` itself is responsible for freeing any other byproducts
 115 //! that may be in play.
 116
 117 pub use self::ScopeId::*;
 118 pub use self::CleanupScopeKind::*;
 119 pub use self::EarlyExitLabel::*;
 120 pub use self::Heap::*;
 121
 122 use llvm::{BasicBlockRef, ValueRef};
 123 use trans::base;
 124 use trans::build;
 125 use trans::common;
 126 use trans::common::{Block, FunctionContext, NodeIdAndSpan};
 127 use trans::debuginfo::{DebugLoc, ToDebugLoc};
 128 use trans::glue;
 129 use middle::region;
 130 use trans::type_::Type;
 131 use middle::ty::{self, Ty};
 132 use std::fmt;
 133 use syntax::ast;
 134
 135 pub struct CleanupScope<'blk, 'tcx: 'blk> {
 136     // The id of this cleanup scope. If the id is None,
 137     // this is a *temporary scope* that is pushed during trans to
 138     // cleanup miscellaneous garbage that trans may generate whose
 139     // lifetime is a subset of some expression.  See module doc for
 140     // more details.
 141     kind: CleanupScopeKind<'blk, 'tcx>,
 142
 143     // Cleanups to run upon scope exit.
 144     cleanups: Vec<CleanupObj<'tcx>>,
 145
 146     // The debug location any drop calls generated for this scope will be
 147     // associated with.
 148     debug_loc: DebugLoc,
 149
 150     cached_early_exits: Vec<CachedEarlyExit>,
 151     cached_landing_pad: Option<BasicBlockRef>,
 152 }
 153
 154 #[derive(Copy, Clone, Debug)]
 155 pub struct CustomScopeIndex {
 156     index: usize
 157 }
 158
 159 pub const EXIT_BREAK: usize = 0;
 160 pub const EXIT_LOOP: usize = 1;
 161 pub const EXIT_MAX: usize = 2;
 162
 163 pub enum CleanupScopeKind<'blk, 'tcx: 'blk> {
 164     CustomScopeKind,
 165     AstScopeKind(ast::NodeId),
 166     LoopScopeKind(ast::NodeId, [Block<'blk, 'tcx>; EXIT_MAX])
 167 }
 168
 169 impl<'blk, 'tcx: 'blk> fmt::Debug for CleanupScopeKind<'blk, 'tcx> {
 170     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 171         match *self {
 172             CustomScopeKind => write!(f, "CustomScopeKind"),
 173             AstScopeKind(nid) => write!(f, "AstScopeKind({})", nid),
 174             LoopScopeKind(nid, ref blks) => {
 175                 try!(write!(f, "LoopScopeKind({}, [", nid));
 176                 for blk in blks {
 177                     try!(write!(f, "{:p}, ", blk));
 178                 }
 179                 write!(f, "])")
 180             }
 181         }
 182     }
 183 }
 184
 185 #[derive(Copy, Clone, PartialEq, Debug)]
 186 pub enum EarlyExitLabel {
 187     UnwindExit,
 188     ReturnExit,
 189     LoopExit(ast::NodeId, usize)
 190 }
 191
 192 #[derive(Copy, Clone)]
 193 pub struct CachedEarlyExit {
 194     label: EarlyExitLabel,
 195     cleanup_block: BasicBlockRef,
 196 }
 197
 198 pub trait Cleanup<'tcx> {
 199     fn must_unwind(&self) -> bool;
 200     fn is_lifetime_end(&self) -> bool;
 201     fn trans<'blk>(&self,
 202                    bcx: Block<'blk, 'tcx>,
 203                    debug_loc: DebugLoc)
 204                    -> Block<'blk, 'tcx>;
 205 }
 206
 207 pub type CleanupObj<'tcx> = Box<Cleanup<'tcx>+'tcx>;
 208
 209 #[derive(Copy, Clone, Debug)]
 210 pub enum ScopeId {
 211     AstScope(ast::NodeId),
 212     CustomScope(CustomScopeIndex)
 213 }
 214
 215 impl<'blk, 'tcx> CleanupMethods<'blk, 'tcx> for FunctionContext<'blk, 'tcx> {
 216     /// Invoked when we start to trans the code contained within a new cleanup scope.
 217     fn push_ast_cleanup_scope(&self, debug_loc: NodeIdAndSpan) {
 218         debug!("push_ast_cleanup_scope({})",
 219                self.ccx.tcx().map.node_to_string(debug_loc.id));
 220
 221         // FIXME(#2202) -- currently closure bodies have a parent
 222         // region, which messes up the assertion below, since there
 223         // are no cleanup scopes on the stack at the start of
 224         // trans'ing a closure body.  I think though that this should
 225         // eventually be fixed by closure bodies not having a parent
 226         // region, though that's a touch unclear, and it might also be
 227         // better just to narrow this assertion more (i.e., by
 228         // excluding id's that correspond to closure bodies only). For
 229         // now we just say that if there is already an AST scope on the stack,
 230         // this new AST scope had better be its immediate child.
 231         let top_scope = self.top_ast_scope();
 232         if top_scope.is_some() {
 233             assert!((self.ccx
 234                      .tcx()
 235                      .region_maps
 236                      .opt_encl_scope(region::CodeExtent::from_node_id(debug_loc.id))
 237                      .map(|s|s.node_id()) == top_scope)
 238                     ||
 239                     (self.ccx
 240                      .tcx()
 241                      .region_maps
 242                      .opt_encl_scope(region::CodeExtent::DestructionScope(debug_loc.id))
 243                      .map(|s|s.node_id()) == top_scope));
 244         }
 245
 246         self.push_scope(CleanupScope::new(AstScopeKind(debug_loc.id),
 247                                           debug_loc.debug_loc()));
 248     }
 249
 250     fn push_loop_cleanup_scope(&self,
 251                                id: ast::NodeId,
 252                                exits: [Block<'blk, 'tcx>; EXIT_MAX]) {
 253         debug!("push_loop_cleanup_scope({})",
 254                self.ccx.tcx().map.node_to_string(id));
 255         assert_eq!(Some(id), self.top_ast_scope());
 256
 257         // Just copy the debuginfo source location from the enclosing scope
 258         let debug_loc = self.scopes
 259                             .borrow()
 260                             .last()
 261                             .unwrap()
 262                             .debug_loc;
 263
 264         self.push_scope(CleanupScope::new(LoopScopeKind(id, exits), debug_loc));
 265     }
 266
 267     fn push_custom_cleanup_scope(&self) -> CustomScopeIndex {
 268         let index = self.scopes_len();
 269         debug!("push_custom_cleanup_scope(): {}", index);
 270
 271         // Just copy the debuginfo source location from the enclosing scope
 272         let debug_loc = self.scopes
 273                             .borrow()
 274                             .last()
 275                             .map(|opt_scope| opt_scope.debug_loc)
 276                             .unwrap_or(DebugLoc::None);
 277
 278         self.push_scope(CleanupScope::new(CustomScopeKind, debug_loc));
 279         CustomScopeIndex { index: index }
 280     }
 281
 282     fn push_custom_cleanup_scope_with_debug_loc(&self,
 283                                                 debug_loc: NodeIdAndSpan)
 284                                                 -> CustomScopeIndex {
 285         let index = self.scopes_len();
 286         debug!("push_custom_cleanup_scope(): {}", index);
 287
 288         self.push_scope(CleanupScope::new(CustomScopeKind,
 289                                           debug_loc.debug_loc()));
 290         CustomScopeIndex { index: index }
 291     }
 292
 293     /// Removes the cleanup scope for id `cleanup_scope`, which must be at the top of the cleanup
 294     /// stack, and generates the code to do its cleanups for normal exit.
 295     fn pop_and_trans_ast_cleanup_scope(&self,
 296                                        bcx: Block<'blk, 'tcx>,
 297                                        cleanup_scope: ast::NodeId)
 298                                        -> Block<'blk, 'tcx> {
 299         debug!("pop_and_trans_ast_cleanup_scope({})",
 300                self.ccx.tcx().map.node_to_string(cleanup_scope));
 301
 302         assert!(self.top_scope(|s| s.kind.is_ast_with_id(cleanup_scope)));
 303
 304         let scope = self.pop_scope();
 305         self.trans_scope_cleanups(bcx, &scope)
 306     }
 307
 308     /// Removes the loop cleanup scope for id `cleanup_scope`, which must be at the top of the
 309     /// cleanup stack. Does not generate any cleanup code, since loop scopes should exit by
 310     /// branching to a block generated by `normal_exit_block`.
 311     fn pop_loop_cleanup_scope(&self,
 312                               cleanup_scope: ast::NodeId) {
 313         debug!("pop_loop_cleanup_scope({})",
 314                self.ccx.tcx().map.node_to_string(cleanup_scope));
 315
 316         assert!(self.top_scope(|s| s.kind.is_loop_with_id(cleanup_scope)));
 317
 318         let _ = self.pop_scope();
 319     }
 320
 321     /// Removes the top cleanup scope from the stack without executing its cleanups. The top
 322     /// cleanup scope must be the temporary scope `custom_scope`.
 323     fn pop_custom_cleanup_scope(&self,
 324                                 custom_scope: CustomScopeIndex) {
 325         debug!("pop_custom_cleanup_scope({})", custom_scope.index);
 326         assert!(self.is_valid_to_pop_custom_scope(custom_scope));
 327         let _ = self.pop_scope();
 328     }
 329
 330     /// Removes the top cleanup scope from the stack, which must be a temporary scope, and
 331     /// generates the code to do its cleanups for normal exit.
 332     fn pop_and_trans_custom_cleanup_scope(&self,
 333                                           bcx: Block<'blk, 'tcx>,
 334                                           custom_scope: CustomScopeIndex)
 335                                           -> Block<'blk, 'tcx> {
 336         debug!("pop_and_trans_custom_cleanup_scope({:?})", custom_scope);
 337         assert!(self.is_valid_to_pop_custom_scope(custom_scope));
 338
 339         let scope = self.pop_scope();
 340         self.trans_scope_cleanups(bcx, &scope)
 341     }
 342
 343     /// Returns the id of the top-most loop scope
 344     fn top_loop_scope(&self) -> ast::NodeId {
 345         for scope in self.scopes.borrow().iter().rev() {
 346             if let LoopScopeKind(id, _) = scope.kind {
 347                 return id;
 348             }
 349         }
 350         self.ccx.sess().bug("no loop scope found");
 351     }
 352
 353     /// Returns a block to branch to which will perform all pending cleanups and then
 354     /// break/continue (depending on `exit`) out of the loop with id `cleanup_scope`
 355     fn normal_exit_block(&'blk self,
 356                          cleanup_scope: ast::NodeId,
 357                          exit: usize) -> BasicBlockRef {
 358         self.trans_cleanups_to_exit_scope(LoopExit(cleanup_scope, exit))
 359     }
 360
 361     /// Returns a block to branch to which will perform all pending cleanups and then return from
 362     /// this function
 363     fn return_exit_block(&'blk self) -> BasicBlockRef {
 364         self.trans_cleanups_to_exit_scope(ReturnExit)
 365     }
 366
 367     fn schedule_lifetime_end(&self,
 368                              cleanup_scope: ScopeId,
 369                              val: ValueRef) {
 370         let drop = box LifetimeEnd {
 371             ptr: val,
 372         };
 373
 374         debug!("schedule_lifetime_end({:?}, val={})",
 375                cleanup_scope,
 376                self.ccx.tn().val_to_string(val));
 377
 378         self.schedule_clean(cleanup_scope, drop as CleanupObj);
 379     }
 380
 381     /// Schedules a (deep) drop of `val`, which is a pointer to an instance of `ty`
 382     fn schedule_drop_mem(&self,
 383                          cleanup_scope: ScopeId,
 384                          val: ValueRef,
 385                          ty: Ty<'tcx>) {
 386         if !self.type_needs_drop(ty) { return; }
 387         let drop = box DropValue {
 388             is_immediate: false,
 389             val: val,
 390             ty: ty,
 391             fill_on_drop: false,
 392             skip_dtor: false,
 393         };
 394
 395         debug!("schedule_drop_mem({:?}, val={}, ty={:?}) fill_on_drop={} skip_dtor={}",
 396                cleanup_scope,
 397                self.ccx.tn().val_to_string(val),
 398                ty,
 399                drop.fill_on_drop,
 400                drop.skip_dtor);
 401
 402         self.schedule_clean(cleanup_scope, drop as CleanupObj);
 403     }
 404
 405     /// Schedules a (deep) drop and filling of `val`, which is a pointer to an instance of `ty`
 406     fn schedule_drop_and_fill_mem(&self,
 407                                   cleanup_scope: ScopeId,
 408                                   val: ValueRef,
 409                                   ty: Ty<'tcx>) {
 410         if !self.type_needs_drop(ty) { return; }
 411
 412         let drop = box DropValue {
 413             is_immediate: false,
 414             val: val,
 415             ty: ty,
 416             fill_on_drop: true,
 417             skip_dtor: false,
 418         };
 419
 420         debug!("schedule_drop_and_fill_mem({:?}, val={}, ty={:?}, fill_on_drop={}, skip_dtor={})",
 421                cleanup_scope,
 422                self.ccx.tn().val_to_string(val),
 423                ty,
 424                drop.fill_on_drop,
 425                drop.skip_dtor);
 426
 427         self.schedule_clean(cleanup_scope, drop as CleanupObj);
 428     }
 429
 430     /// Issue #23611: Schedules a (deep) drop of the contents of
 431     /// `val`, which is a pointer to an instance of struct/enum type
 432     /// `ty`. The scheduled code handles extracting the discriminant
 433     /// and dropping the contents associated with that variant
 434     /// *without* executing any associated drop implementation.
 435     fn schedule_drop_adt_contents(&self,
 436                                   cleanup_scope: ScopeId,
 437                                   val: ValueRef,
 438                                   ty: Ty<'tcx>) {
 439         // `if` below could be "!contents_needs_drop"; skipping drop
 440         // is just an optimization, so sound to be conservative.
 441         if !self.type_needs_drop(ty) { return; }
 442
 443         let drop = box DropValue {
 444             is_immediate: false,
 445             val: val,
 446             ty: ty,
 447             fill_on_drop: false,
 448             skip_dtor: true,
 449         };
 450
 451         debug!("schedule_drop_adt_contents({:?}, val={}, ty={:?}) fill_on_drop={} skip_dtor={}",
 452                cleanup_scope,
 453                self.ccx.tn().val_to_string(val),
 454                ty,
 455                drop.fill_on_drop,
 456                drop.skip_dtor);
 457
 458         self.schedule_clean(cleanup_scope, drop as CleanupObj);
 459     }
 460
 461     /// Schedules a (deep) drop of `val`, which is an instance of `ty`
 462     fn schedule_drop_immediate(&self,
 463                                cleanup_scope: ScopeId,
 464                                val: ValueRef,
 465                                ty: Ty<'tcx>) {
 466
 467         if !self.type_needs_drop(ty) { return; }
 468         let drop = box DropValue {
 469             is_immediate: true,
 470             val: val,
 471             ty: ty,
 472             fill_on_drop: false,
 473             skip_dtor: false,
 474         };
 475
 476         debug!("schedule_drop_immediate({:?}, val={}, ty={:?}) fill_on_drop={} skip_dtor={}",
 477                cleanup_scope,
 478                self.ccx.tn().val_to_string(val),
 479                ty,
 480                drop.fill_on_drop,
 481                drop.skip_dtor);
 482
 483         self.schedule_clean(cleanup_scope, drop as CleanupObj);
 484     }
 485
 486     /// Schedules a call to `free(val)`. Note that this is a shallow operation.
 487     fn schedule_free_value(&self,
 488                            cleanup_scope: ScopeId,
 489                            val: ValueRef,
 490                            heap: Heap,
 491                            content_ty: Ty<'tcx>) {
 492         let drop = box FreeValue { ptr: val, heap: heap, content_ty: content_ty };
 493
 494         debug!("schedule_free_value({:?}, val={}, heap={:?})",
 495                cleanup_scope,
 496                self.ccx.tn().val_to_string(val),
 497                heap);
 498
 499         self.schedule_clean(cleanup_scope, drop as CleanupObj);
 500     }
 501
 502     fn schedule_clean(&self,
 503                       cleanup_scope: ScopeId,
 504                       cleanup: CleanupObj<'tcx>) {
 505         match cleanup_scope {
 506             AstScope(id) => self.schedule_clean_in_ast_scope(id, cleanup),
 507             CustomScope(id) => self.schedule_clean_in_custom_scope(id, cleanup),
 508         }
 509     }
 510
 511     /// Schedules a cleanup to occur upon exit from `cleanup_scope`. If `cleanup_scope` is not
 512     /// provided, then the cleanup is scheduled in the topmost scope, which must be a temporary
 513     /// scope.
 514     fn schedule_clean_in_ast_scope(&self,
 515                                    cleanup_scope: ast::NodeId,
 516                                    cleanup: CleanupObj<'tcx>) {
 517         debug!("schedule_clean_in_ast_scope(cleanup_scope={})",
 518                cleanup_scope);
 519
 520         for scope in self.scopes.borrow_mut().iter_mut().rev() {
 521             if scope.kind.is_ast_with_id(cleanup_scope) {
 522                 scope.cleanups.push(cleanup);
 523                 scope.clear_cached_exits();
 524                 return;
 525             } else {
 526                 // will be adding a cleanup to some enclosing scope
 527                 scope.clear_cached_exits();
 528             }
 529         }
 530
 531         self.ccx.sess().bug(
 532             &format!("no cleanup scope {} found",
 533                     self.ccx.tcx().map.node_to_string(cleanup_scope)));
 534     }
 535
 536     /// Schedules a cleanup to occur in the top-most scope, which must be a temporary scope.
 537     fn schedule_clean_in_custom_scope(&self,
 538                                       custom_scope: CustomScopeIndex,
 539                                       cleanup: CleanupObj<'tcx>) {
 540         debug!("schedule_clean_in_custom_scope(custom_scope={})",
 541                custom_scope.index);
 542
 543         assert!(self.is_valid_custom_scope(custom_scope));
 544
 545         let mut scopes = self.scopes.borrow_mut();
 546         let scope = &mut (*scopes)[custom_scope.index];
 547         scope.cleanups.push(cleanup);
 548         scope.clear_cached_exits();
 549     }
 550
 551     /// Returns true if there are pending cleanups that should execute on panic.
 552     fn needs_invoke(&self) -> bool {
 553         self.scopes.borrow().iter().rev().any(|s| s.needs_invoke())
 554     }
 555
 556     /// Returns a basic block to branch to in the event of a panic. This block will run the panic
 557     /// cleanups and eventually invoke the LLVM `Resume` instruction.
 558     fn get_landing_pad(&'blk self) -> BasicBlockRef {
 559         let _icx = base::push_ctxt("get_landing_pad");
 560
 561         debug!("get_landing_pad");
 562
 563         let orig_scopes_len = self.scopes_len();
 564         assert!(orig_scopes_len > 0);
 565
 566         // Remove any scopes that do not have cleanups on panic:
 567         let mut popped_scopes = vec!();
 568         while !self.top_scope(|s| s.needs_invoke()) {
 569             debug!("top scope does not need invoke");
 570             popped_scopes.push(self.pop_scope());
 571         }
 572
 573         // Check for an existing landing pad in the new topmost scope:
 574         let llbb = self.get_or_create_landing_pad();
 575
 576         // Push the scopes we removed back on:
 577         loop {
 578             match popped_scopes.pop() {
 579                 Some(scope) => self.push_scope(scope),
 580                 None => break
 581             }
 582         }
 583
 584         assert_eq!(self.scopes_len(), orig_scopes_len);
 585
 586         return llbb;
 587     }
 588 }
 589
 590 impl<'blk, 'tcx> CleanupHelperMethods<'blk, 'tcx> for FunctionContext<'blk, 'tcx> {
 591     /// Returns the id of the current top-most AST scope, if any.
 592     fn top_ast_scope(&self) -> Option<ast::NodeId> {
 593         for scope in self.scopes.borrow().iter().rev() {
 594             match scope.kind {
 595                 CustomScopeKind | LoopScopeKind(..) => {}
 596                 AstScopeKind(i) => {
 597                     return Some(i);
 598                 }
 599             }
 600         }
 601         None
 602     }
 603
 604     fn top_nonempty_cleanup_scope(&self) -> Option<usize> {
 605         self.scopes.borrow().iter().rev().position(|s| !s.cleanups.is_empty())
 606     }
 607
 608     fn is_valid_to_pop_custom_scope(&self, custom_scope: CustomScopeIndex) -> bool {
 609         self.is_valid_custom_scope(custom_scope) &&
 610             custom_scope.index == self.scopes.borrow().len() - 1
 611     }
 612
 613     fn is_valid_custom_scope(&self, custom_scope: CustomScopeIndex) -> bool {
 614         let scopes = self.scopes.borrow();
 615         custom_scope.index < scopes.len() &&
 616             (*scopes)[custom_scope.index].kind.is_temp()
 617     }
 618
 619     /// Generates the cleanups for `scope` into `bcx`
 620     fn trans_scope_cleanups(&self, // cannot borrow self, will recurse
 621                             bcx: Block<'blk, 'tcx>,
 622                             scope: &CleanupScope<'blk, 'tcx>) -> Block<'blk, 'tcx> {
 623
 624         let mut bcx = bcx;
 625         if !bcx.unreachable.get() {
 626             for cleanup in scope.cleanups.iter().rev() {
 627                 bcx = cleanup.trans(bcx, scope.debug_loc);
 628             }
 629         }
 630         bcx
 631     }
 632
 633     fn scopes_len(&self) -> usize {
 634         self.scopes.borrow().len()
 635     }
 636
 637     fn push_scope(&self, scope: CleanupScope<'blk, 'tcx>) {
 638         self.scopes.borrow_mut().push(scope)
 639     }
 640
 641     fn pop_scope(&self) -> CleanupScope<'blk, 'tcx> {
 642         debug!("popping cleanup scope {}, {} scopes remaining",
 643                self.top_scope(|s| s.block_name("")),
 644                self.scopes_len() - 1);
 645
 646         self.scopes.borrow_mut().pop().unwrap()
 647     }
 648
 649     fn top_scope<R, F>(&self, f: F) -> R where F: FnOnce(&CleanupScope<'blk, 'tcx>) -> R {
 650         f(self.scopes.borrow().last().unwrap())
 651     }
 652
 653     /// Used when the caller wishes to jump to an early exit, such as a return, break, continue, or
 654     /// unwind. This function will generate all cleanups between the top of the stack and the exit
 655     /// `label` and return a basic block that the caller can branch to.
 656     ///
 657     /// For example, if the current stack of cleanups were as follows:
 658     ///
 659     ///      AST 22
 660     ///      Custom 1
 661     ///      AST 23
 662     ///      Loop 23
 663     ///      Custom 2
 664     ///      AST 24
 665     ///
 666     /// and the `label` specifies a break from `Loop 23`, then this function would generate a
 667     /// series of basic blocks as follows:
 668     ///
 669     ///      Cleanup(AST 24) -> Cleanup(Custom 2) -> break_blk
 670     ///
 671     /// where `break_blk` is the block specified in `Loop 23` as the target for breaks. The return
 672     /// value would be the first basic block in that sequence (`Cleanup(AST 24)`). The caller could
 673     /// then branch to `Cleanup(AST 24)` and it will perform all cleanups and finally branch to the
 674     /// `break_blk`.
 675     fn trans_cleanups_to_exit_scope(&'blk self,
 676                                     label: EarlyExitLabel)
 677                                     -> BasicBlockRef {
 678         debug!("trans_cleanups_to_exit_scope label={:?} scopes={}",
 679                label, self.scopes_len());
 680
 681         let orig_scopes_len = self.scopes_len();
 682         let mut prev_llbb;
 683         let mut popped_scopes = vec!();
 684
 685         // First we pop off all the cleanup stacks that are
 686         // traversed until the exit is reached, pushing them
 687         // onto the side vector `popped_scopes`. No code is
 688         // generated at this time.
 689         //
 690         // So, continuing the example from above, we would wind up
 691         // with a `popped_scopes` vector of `[AST 24, Custom 2]`.
 692         // (Presuming that there are no cached exits)
 693         loop {
 694             if self.scopes_len() == 0 {
 695                 match label {
 696                     UnwindExit => {
 697                         // Generate a block that will `Resume`.
 698                         let prev_bcx = self.new_block(true, "resume", None);
 699                         let personality = self.personality.get().expect(
 700                             "create_landing_pad() should have set this");
 701                         build::Resume(prev_bcx,
 702                                       build::Load(prev_bcx, personality));
 703                         prev_llbb = prev_bcx.llbb;
 704                         break;
 705                     }
 706
 707                     ReturnExit => {
 708                         prev_llbb = self.get_llreturn();
 709                         break;
 710                     }
 711
 712                     LoopExit(id, _) => {
 713                         self.ccx.sess().bug(&format!(
 714                                 "cannot exit from scope {}, \
 715                                 not in scope", id));
 716                     }
 717                 }
 718             }
 719
 720             // Check if we have already cached the unwinding of this
 721             // scope for this label. If so, we can stop popping scopes
 722             // and branch to the cached label, since it contains the
 723             // cleanups for any subsequent scopes.
 724             match self.top_scope(|s| s.cached_early_exit(label)) {
 725                 Some(cleanup_block) => {
 726                     prev_llbb = cleanup_block;
 727                     break;
 728                 }
 729                 None => { }
 730             }
 731
 732             // Pop off the scope, since we will be generating
 733             // unwinding code for it. If we are searching for a loop exit,
 734             // and this scope is that loop, then stop popping and set
 735             // `prev_llbb` to the appropriate exit block from the loop.
 736             popped_scopes.push(self.pop_scope());
 737             let scope = popped_scopes.last().unwrap();
 738             match label {
 739                 UnwindExit | ReturnExit => { }
 740                 LoopExit(id, exit) => {
 741                     match scope.kind.early_exit_block(id, exit) {
 742                         Some(exitllbb) => {
 743                             prev_llbb = exitllbb;
 744                             break;
 745                         }
 746
 747                         None => { }
 748                     }
 749                 }
 750             }
 751         }
 752
 753         debug!("trans_cleanups_to_exit_scope: popped {} scopes",
 754                popped_scopes.len());
 755
 756         // Now push the popped scopes back on. As we go,
 757         // we track in `prev_llbb` the exit to which this scope
 758         // should branch when it's done.
 759         //
 760         // So, continuing with our example, we will start out with
 761         // `prev_llbb` being set to `break_blk` (or possibly a cached
 762         // early exit). We will then pop the scopes from `popped_scopes`
 763         // and generate a basic block for each one, prepending it in the
 764         // series and updating `prev_llbb`. So we begin by popping `Custom 2`
 765         // and generating `Cleanup(Custom 2)`. We make `Cleanup(Custom 2)`
 766         // branch to `prev_llbb == break_blk`, giving us a sequence like:
 767         //
 768         //     Cleanup(Custom 2) -> prev_llbb
 769         //
 770         // We then pop `AST 24` and repeat the process, giving us the sequence:
 771         //
 772         //     Cleanup(AST 24) -> Cleanup(Custom 2) -> prev_llbb
 773         //
 774         // At this point, `popped_scopes` is empty, and so the final block
 775         // that we return to the user is `Cleanup(AST 24)`.
 776         while let Some(mut scope) = popped_scopes.pop() {
 777             if !scope.cleanups.is_empty() {
 778                 let name = scope.block_name("clean");
 779                 debug!("generating cleanups for {}", name);
 780                 let bcx_in = self.new_block(label.is_unwind(),
 781                                             &name[..],
 782                                             None);
 783                 let mut bcx_out = bcx_in;
 784                 for cleanup in scope.cleanups.iter().rev() {
 785                     bcx_out = cleanup.trans(bcx_out,
 786                                             scope.debug_loc);
 787                 }
 788                 build::Br(bcx_out, prev_llbb, DebugLoc::None);
 789                 prev_llbb = bcx_in.llbb;
 790
 791                 scope.add_cached_early_exit(label, prev_llbb);
 792             }
 793             self.push_scope(scope);
 794         }
 795
 796         debug!("trans_cleanups_to_exit_scope: prev_llbb={:?}", prev_llbb);
 797
 798         assert_eq!(self.scopes_len(), orig_scopes_len);
 799         prev_llbb
 800     }
 801
 802     /// Creates a landing pad for the top scope, if one does not exist.  The landing pad will
 803     /// perform all cleanups necessary for an unwind and then `resume` to continue error
 804     /// propagation:
 805     ///
 806     ///     landing_pad -> ... cleanups ... -> [resume]
 807     ///
 808     /// (The cleanups and resume instruction are created by `trans_cleanups_to_exit_scope()`, not
 809     /// in this function itself.)
 810     fn get_or_create_landing_pad(&'blk self) -> BasicBlockRef {
 811         let pad_bcx;
 812
 813         debug!("get_or_create_landing_pad");
 814
 815         // Check if a landing pad block exists; if not, create one.
 816         {
 817             let mut scopes = self.scopes.borrow_mut();
 818             let last_scope = scopes.last_mut().unwrap();
 819             match last_scope.cached_landing_pad {
 820                 Some(llbb) => { return llbb; }
 821                 None => {
 822                     let name = last_scope.block_name("unwind");
 823                     pad_bcx = self.new_block(true, &name[..], None);
 824                     last_scope.cached_landing_pad = Some(pad_bcx.llbb);
 825                 }
 826             }
 827         }
 828
 829         // The landing pad return type (the type being propagated). Not sure what
 830         // this represents but it's determined by the personality function and
 831         // this is what the EH proposal example uses.
 832         let llretty = Type::struct_(self.ccx,
 833                                     &[Type::i8p(self.ccx), Type::i32(self.ccx)],
 834                                     false);
 835
 836         let llpersonality = pad_bcx.fcx.eh_personality();
 837
 838         // The only landing pad clause will be 'cleanup'
 839         let llretval = build::LandingPad(pad_bcx, llretty, llpersonality, 1);
 840
 841         // The landing pad block is a cleanup
 842         build::SetCleanup(pad_bcx, llretval);
 843
 844         // We store the retval in a function-central alloca, so that calls to
 845         // Resume can find it.
 846         match self.personality.get() {
 847             Some(addr) => {
 848                 build::Store(pad_bcx, llretval, addr);
 849             }
 850             None => {
 851                 let addr = base::alloca(pad_bcx, common::val_ty(llretval), "");
 852                 self.personality.set(Some(addr));
 853                 build::Store(pad_bcx, llretval, addr);
 854             }
 855         }
 856
 857         // Generate the cleanup block and branch to it.
 858         let cleanup_llbb = self.trans_cleanups_to_exit_scope(UnwindExit);
 859         build::Br(pad_bcx, cleanup_llbb, DebugLoc::None);
 860
 861         return pad_bcx.llbb;
 862     }
 863 }
 864
 865 impl<'blk, 'tcx> CleanupScope<'blk, 'tcx> {
 866     fn new(kind: CleanupScopeKind<'blk, 'tcx>,
 867            debug_loc: DebugLoc)
 868         -> CleanupScope<'blk, 'tcx> {
 869         CleanupScope {
 870             kind: kind,
 871             debug_loc: debug_loc,
 872             cleanups: vec!(),
 873             cached_early_exits: vec!(),
 874             cached_landing_pad: None,
 875         }
 876     }
 877
 878     fn clear_cached_exits(&mut self) {
 879         self.cached_early_exits = vec!();
 880         self.cached_landing_pad = None;
 881     }
 882
 883     fn cached_early_exit(&self,
 884                          label: EarlyExitLabel)
 885                          -> Option<BasicBlockRef> {
 886         self.cached_early_exits.iter().
 887             find(|e| e.label == label).
 888             map(|e| e.cleanup_block)
 889     }
 890
 891     fn add_cached_early_exit(&mut self,
 892                              label: EarlyExitLabel,
 893                              blk: BasicBlockRef) {
 894         self.cached_early_exits.push(
 895             CachedEarlyExit { label: label,
 896                               cleanup_block: blk });
 897     }
 898
 899     /// True if this scope has cleanups that need unwinding
 900     fn needs_invoke(&self) -> bool {
 901
 902         self.cached_landing_pad.is_some() ||
 903             self.cleanups.iter().any(|c| c.must_unwind())
 904     }
 905
 906     /// Returns a suitable name to use for the basic block that handles this cleanup scope
 907     fn block_name(&self, prefix: &str) -> String {
 908         match self.kind {
 909             CustomScopeKind => format!("{}_custom_", prefix),
 910             AstScopeKind(id) => format!("{}_ast_{}_", prefix, id),
 911             LoopScopeKind(id, _) => format!("{}_loop_{}_", prefix, id),
 912         }
 913     }
 914
 915     /// Manipulate cleanup scope for call arguments. Conceptually, each
 916     /// argument to a call is an lvalue, and performing the call moves each
 917     /// of the arguments into a new rvalue (which gets cleaned up by the
 918     /// callee). As an optimization, instead of actually performing all of
 919     /// those moves, trans just manipulates the cleanup scope to obtain the
 920     /// same effect.
 921     pub fn drop_non_lifetime_clean(&mut self) {
 922         self.cleanups.retain(|c| c.is_lifetime_end());
 923         self.clear_cached_exits();
 924     }
 925 }
 926
 927 impl<'blk, 'tcx> CleanupScopeKind<'blk, 'tcx> {
 928     fn is_temp(&self) -> bool {
 929         match *self {
 930             CustomScopeKind => true,
 931             LoopScopeKind(..) | AstScopeKind(..) => false,
 932         }
 933     }
 934
 935     fn is_ast_with_id(&self, id: ast::NodeId) -> bool {
 936         match *self {
 937             CustomScopeKind | LoopScopeKind(..) => false,
 938             AstScopeKind(i) => i == id
 939         }
 940     }
 941
 942     fn is_loop_with_id(&self, id: ast::NodeId) -> bool {
 943         match *self {
 944             CustomScopeKind | AstScopeKind(..) => false,
 945             LoopScopeKind(i, _) => i == id
 946         }
 947     }
 948
 949     /// If this is a loop scope with id `id`, return the early exit block `exit`, else `None`
 950     fn early_exit_block(&self,
 951                         id: ast::NodeId,
 952                         exit: usize) -> Option<BasicBlockRef> {
 953         match *self {
 954             LoopScopeKind(i, ref exits) if id == i => Some(exits[exit].llbb),
 955             _ => None,
 956         }
 957     }
 958 }
 959
 960 impl EarlyExitLabel {
 961     fn is_unwind(&self) -> bool {
 962         match *self {
 963             UnwindExit => true,
 964             _ => false
 965         }
 966     }
 967 }
 968
 969 ///////////////////////////////////////////////////////////////////////////
 970 // Cleanup types
 971
 972 #[derive(Copy, Clone)]
 973 pub struct DropValue<'tcx> {
 974     is_immediate: bool,
 975     val: ValueRef,
 976     ty: Ty<'tcx>,
 977     fill_on_drop: bool,
 978     skip_dtor: bool,
 979 }
 980
 981 impl<'tcx> Cleanup<'tcx> for DropValue<'tcx> {
 982     fn must_unwind(&self) -> bool {
 983         true
 984     }
 985
 986     fn is_lifetime_end(&self) -> bool {
 987         false
 988     }
 989
 990     fn trans<'blk>(&self,
 991                    bcx: Block<'blk, 'tcx>,
 992                    debug_loc: DebugLoc)
 993                    -> Block<'blk, 'tcx> {
 994         let skip_dtor = self.skip_dtor;
 995         let _icx = if skip_dtor {
 996             base::push_ctxt("<DropValue as Cleanup>::trans skip_dtor=true")
 997         } else {
 998             base::push_ctxt("<DropValue as Cleanup>::trans skip_dtor=false")
 999         };
1000         let bcx = if self.is_immediate {
1001             glue::drop_ty_immediate(bcx, self.val, self.ty, debug_loc, self.skip_dtor)
1002         } else {
1003             glue::drop_ty_core(bcx, self.val, self.ty, debug_loc, self.skip_dtor)
1004         };
1005         if self.fill_on_drop {
1006             base::drop_done_fill_mem(bcx, self.val, self.ty);
1007         }
1008         bcx
1009     }
1010 }
1011
1012 #[derive(Copy, Clone, Debug)]
1013 pub enum Heap {
1014     HeapExchange
1015 }
1016
1017 #[derive(Copy, Clone)]
1018 pub struct FreeValue<'tcx> {
1019     ptr: ValueRef,
1020     heap: Heap,
1021     content_ty: Ty<'tcx>
1022 }
1023
1024 impl<'tcx> Cleanup<'tcx> for FreeValue<'tcx> {
1025     fn must_unwind(&self) -> bool {
1026         true
1027     }
1028
1029     fn is_lifetime_end(&self) -> bool {
1030         false
1031     }
1032
1033     fn trans<'blk>(&self,
1034                    bcx: Block<'blk, 'tcx>,
1035                    debug_loc: DebugLoc)
1036                    -> Block<'blk, 'tcx> {
1037         match self.heap {
1038             HeapExchange => {
1039                 glue::trans_exchange_free_ty(bcx,
1040                                              self.ptr,
1041                                              self.content_ty,
1042                                              debug_loc)
1043             }
1044         }
1045     }
1046 }
1047
1048 #[derive(Copy, Clone)]
1049 pub struct LifetimeEnd {
1050     ptr: ValueRef,
1051 }
1052
1053 impl<'tcx> Cleanup<'tcx> for LifetimeEnd {
1054     fn must_unwind(&self) -> bool {
1055         false
1056     }
1057
1058     fn is_lifetime_end(&self) -> bool {
1059         true
1060     }
1061
1062     fn trans<'blk>(&self,
1063                    bcx: Block<'blk, 'tcx>,
1064                    debug_loc: DebugLoc)
1065                    -> Block<'blk, 'tcx> {
1066         debug_loc.apply(bcx.fcx);
1067         base::call_lifetime_end(bcx, self.ptr);
1068         bcx
1069     }
1070 }
1071
1072 pub fn temporary_scope(tcx: &ty::ctxt,
1073                        id: ast::NodeId)
1074                        -> ScopeId {
1075     match tcx.region_maps.temporary_scope(id) {
1076         Some(scope) => {
1077             let r = AstScope(scope.node_id());
1078             debug!("temporary_scope({}) = {:?}", id, r);
1079             r
1080         }
1081         None => {
1082             tcx.sess.bug(&format!("no temporary scope available for expr {}",
1083                                  id))
1084         }
1085     }
1086 }
1087
1088 pub fn var_scope(tcx: &ty::ctxt,
1089                  id: ast::NodeId)
1090                  -> ScopeId {
1091     let r = AstScope(tcx.region_maps.var_scope(id).node_id());
1092     debug!("var_scope({}) = {:?}", id, r);
1093     r
1094 }
1095
1096 ///////////////////////////////////////////////////////////////////////////
1097 // These traits just exist to put the methods into this file.
1098
1099 pub trait CleanupMethods<'blk, 'tcx> {
1100     fn push_ast_cleanup_scope(&self, id: NodeIdAndSpan);
1101     fn push_loop_cleanup_scope(&self,
1102                                id: ast::NodeId,
1103                                exits: [Block<'blk, 'tcx>; EXIT_MAX]);
1104     fn push_custom_cleanup_scope(&self) -> CustomScopeIndex;
1105     fn push_custom_cleanup_scope_with_debug_loc(&self,
1106                                                 debug_loc: NodeIdAndSpan)
1107                                                 -> CustomScopeIndex;
1108     fn pop_and_trans_ast_cleanup_scope(&self,
1109                                        bcx: Block<'blk, 'tcx>,
1110                                        cleanup_scope: ast::NodeId)
1111                                        -> Block<'blk, 'tcx>;
1112     fn pop_loop_cleanup_scope(&self,
1113                               cleanup_scope: ast::NodeId);
1114     fn pop_custom_cleanup_scope(&self,
1115                                 custom_scope: CustomScopeIndex);
1116     fn pop_and_trans_custom_cleanup_scope(&self,
1117                                           bcx: Block<'blk, 'tcx>,
1118                                           custom_scope: CustomScopeIndex)
1119                                           -> Block<'blk, 'tcx>;
1120     fn top_loop_scope(&self) -> ast::NodeId;
1121     fn normal_exit_block(&'blk self,
1122                          cleanup_scope: ast::NodeId,
1123                          exit: usize) -> BasicBlockRef;
1124     fn return_exit_block(&'blk self) -> BasicBlockRef;
1125     fn schedule_lifetime_end(&self,
1126                          cleanup_scope: ScopeId,
1127                          val: ValueRef);
1128     fn schedule_drop_mem(&self,
1129                          cleanup_scope: ScopeId,
1130                          val: ValueRef,
1131                          ty: Ty<'tcx>);
1132     fn schedule_drop_and_fill_mem(&self,
1133                                   cleanup_scope: ScopeId,
1134                                   val: ValueRef,
1135                                   ty: Ty<'tcx>);
1136     fn schedule_drop_adt_contents(&self,
1137                                   cleanup_scope: ScopeId,
1138                                   val: ValueRef,
1139                                   ty: Ty<'tcx>);
1140     fn schedule_drop_immediate(&self,
1141                                cleanup_scope: ScopeId,
1142                                val: ValueRef,
1143                                ty: Ty<'tcx>);
1144     fn schedule_free_value(&self,
1145                            cleanup_scope: ScopeId,
1146                            val: ValueRef,
1147                            heap: Heap,
1148                            content_ty: Ty<'tcx>);
1149     fn schedule_clean(&self,
1150                       cleanup_scope: ScopeId,
1151                       cleanup: CleanupObj<'tcx>);
1152     fn schedule_clean_in_ast_scope(&self,
1153                                    cleanup_scope: ast::NodeId,
1154                                    cleanup: CleanupObj<'tcx>);
1155     fn schedule_clean_in_custom_scope(&self,
1156                                     custom_scope: CustomScopeIndex,
1157                                     cleanup: CleanupObj<'tcx>);
1158     fn needs_invoke(&self) -> bool;
1159     fn get_landing_pad(&'blk self) -> BasicBlockRef;
1160 }
1161
1162 trait CleanupHelperMethods<'blk, 'tcx> {
1163     fn top_ast_scope(&self) -> Option<ast::NodeId>;
1164     fn top_nonempty_cleanup_scope(&self) -> Option<usize>;
1165     fn is_valid_to_pop_custom_scope(&self, custom_scope: CustomScopeIndex) -> bool;
1166     fn is_valid_custom_scope(&self, custom_scope: CustomScopeIndex) -> bool;
1167     fn trans_scope_cleanups(&self,
1168                             bcx: Block<'blk, 'tcx>,
1169                             scope: &CleanupScope<'blk, 'tcx>) -> Block<'blk, 'tcx>;
1170     fn trans_cleanups_to_exit_scope(&'blk self,
1171                                     label: EarlyExitLabel)
1172                                     -> BasicBlockRef;
1173     fn get_or_create_landing_pad(&'blk self) -> BasicBlockRef;
1174     fn scopes_len(&self) -> usize;
1175     fn push_scope(&self, scope: CleanupScope<'blk, 'tcx>);
1176     fn pop_scope(&self) -> CleanupScope<'blk, 'tcx>;
1177     fn top_scope<R, F>(&self, f: F) -> R where F: FnOnce(&CleanupScope<'blk, 'tcx>) -> R;
1178 }