src/librustc_borrowck/borrowck/mir/elaborate_drops.rs

   1 // Copyright 2016 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 super::gather_moves::{HasMoveData, MoveData, MovePathIndex, LookupResult};
  12 use super::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
  13 use super::dataflow::{DataflowResults};
  14 use super::{drop_flag_effects_for_location, on_all_children_bits};
  15 use super::on_lookup_result_bits;
  16 use super::{DropFlagState, MoveDataParamEnv};
  17 use super::patch::MirPatch;
  18 use rustc::ty::{self, Ty, TyCtxt};
  19 use rustc::ty::subst::{Kind, Subst, Substs};
  20 use rustc::mir::*;
  21 use rustc::mir::transform::{Pass, MirPass, MirSource};
  22 use rustc::middle::const_val::ConstVal;
  23 use rustc::middle::lang_items;
  24 use rustc::util::nodemap::FxHashMap;
  25 use rustc_data_structures::indexed_set::IdxSetBuf;
  26 use rustc_data_structures::indexed_vec::Idx;
  27 use syntax_pos::Span;
  28
  29 use std::fmt;
  30 use std::iter;
  31 use std::u32;
  32
  33 pub struct ElaborateDrops;
  34
  35 impl<'tcx> MirPass<'tcx> for ElaborateDrops {
  36     fn run_pass<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
  37                     src: MirSource, mir: &mut Mir<'tcx>)
  38     {
  39         debug!("elaborate_drops({:?} @ {:?})", src, mir.span);
  40         match src {
  41             MirSource::Fn(..) => {},
  42             _ => return
  43         }
  44         let id = src.item_id();
  45         let param_env = ty::ParameterEnvironment::for_item(tcx, id);
  46         let move_data = MoveData::gather_moves(mir, tcx, &param_env);
  47         let elaborate_patch = {
  48             let mir = &*mir;
  49             let env = MoveDataParamEnv {
  50                 move_data: move_data,
  51                 param_env: param_env
  52             };
  53             let flow_inits =
  54                 super::do_dataflow(tcx, mir, id, &[],
  55                                    MaybeInitializedLvals::new(tcx, mir, &env),
  56                                    |bd, p| &bd.move_data().move_paths[p]);
  57             let flow_uninits =
  58                 super::do_dataflow(tcx, mir, id, &[],
  59                                    MaybeUninitializedLvals::new(tcx, mir, &env),
  60                                    |bd, p| &bd.move_data().move_paths[p]);
  61
  62             ElaborateDropsCtxt {
  63                 tcx: tcx,
  64                 mir: mir,
  65                 env: &env,
  66                 flow_inits: flow_inits,
  67                 flow_uninits: flow_uninits,
  68                 drop_flags: FxHashMap(),
  69                 patch: MirPatch::new(mir),
  70             }.elaborate()
  71         };
  72         elaborate_patch.apply(mir);
  73     }
  74 }
  75
  76 impl Pass for ElaborateDrops {}
  77
  78 struct InitializationData {
  79     live: IdxSetBuf<MovePathIndex>,
  80     dead: IdxSetBuf<MovePathIndex>
  81 }
  82
  83 impl InitializationData {
  84     fn apply_location<'a,'tcx>(&mut self,
  85                                tcx: TyCtxt<'a, 'tcx, 'tcx>,
  86                                mir: &Mir<'tcx>,
  87                                env: &MoveDataParamEnv<'tcx>,
  88                                loc: Location)
  89     {
  90         drop_flag_effects_for_location(tcx, mir, env, loc, |path, df| {
  91             debug!("at location {:?}: setting {:?} to {:?}",
  92                    loc, path, df);
  93             match df {
  94                 DropFlagState::Present => {
  95                     self.live.add(&path);
  96                     self.dead.remove(&path);
  97                 }
  98                 DropFlagState::Absent => {
  99                     self.dead.add(&path);
 100                     self.live.remove(&path);
 101                 }
 102             }
 103         });
 104     }
 105
 106     fn state(&self, path: MovePathIndex) -> (bool, bool) {
 107         (self.live.contains(&path), self.dead.contains(&path))
 108     }
 109 }
 110
 111 impl fmt::Debug for InitializationData {
 112     fn fmt(&self, _f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
 113         Ok(())
 114     }
 115 }
 116
 117 struct ElaborateDropsCtxt<'a, 'tcx: 'a> {
 118     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 119     mir: &'a Mir<'tcx>,
 120     env: &'a MoveDataParamEnv<'tcx>,
 121     flow_inits: DataflowResults<MaybeInitializedLvals<'a, 'tcx>>,
 122     flow_uninits:  DataflowResults<MaybeUninitializedLvals<'a, 'tcx>>,
 123     drop_flags: FxHashMap<MovePathIndex, Local>,
 124     patch: MirPatch<'tcx>,
 125 }
 126
 127 #[derive(Copy, Clone, Debug)]
 128 struct DropCtxt<'a, 'tcx: 'a> {
 129     source_info: SourceInfo,
 130     is_cleanup: bool,
 131
 132     init_data: &'a InitializationData,
 133
 134     lvalue: &'a Lvalue<'tcx>,
 135     path: MovePathIndex,
 136     succ: BasicBlock,
 137     unwind: Option<BasicBlock>
 138 }
 139
 140 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
 141     fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
 142     fn param_env(&self) -> &'b ty::ParameterEnvironment<'tcx> {
 143         &self.env.param_env
 144     }
 145
 146     fn initialization_data_at(&self, loc: Location) -> InitializationData {
 147         let mut data = InitializationData {
 148             live: self.flow_inits.sets().on_entry_set_for(loc.block.index())
 149                 .to_owned(),
 150             dead: self.flow_uninits.sets().on_entry_set_for(loc.block.index())
 151                 .to_owned(),
 152         };
 153         for stmt in 0..loc.statement_index {
 154             data.apply_location(self.tcx, self.mir, self.env,
 155                                 Location { block: loc.block, statement_index: stmt });
 156         }
 157         data
 158     }
 159
 160     fn create_drop_flag(&mut self, index: MovePathIndex) {
 161         let tcx = self.tcx;
 162         let patch = &mut self.patch;
 163         self.drop_flags.entry(index).or_insert_with(|| {
 164             patch.new_temp(tcx.types.bool)
 165         });
 166     }
 167
 168     fn drop_flag(&mut self, index: MovePathIndex) -> Option<Lvalue<'tcx>> {
 169         self.drop_flags.get(&index).map(|t| Lvalue::Local(*t))
 170     }
 171
 172     /// create a patch that elaborates all drops in the input
 173     /// MIR.
 174     fn elaborate(mut self) -> MirPatch<'tcx>
 175     {
 176         self.collect_drop_flags();
 177
 178         self.elaborate_drops();
 179
 180         self.drop_flags_on_init();
 181         self.drop_flags_for_fn_rets();
 182         self.drop_flags_for_args();
 183         self.drop_flags_for_locs();
 184
 185         self.patch
 186     }
 187
 188     fn path_needs_drop(&self, path: MovePathIndex) -> bool
 189     {
 190         let lvalue = &self.move_data().move_paths[path].lvalue;
 191         let ty = lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
 192         debug!("path_needs_drop({:?}, {:?} : {:?})", path, lvalue, ty);
 193
 194         self.tcx.type_needs_drop_given_env(ty, self.param_env())
 195     }
 196
 197     fn collect_drop_flags(&mut self)
 198     {
 199         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
 200             let terminator = data.terminator();
 201             let location = match terminator.kind {
 202                 TerminatorKind::Drop { ref location, .. } |
 203                 TerminatorKind::DropAndReplace { ref location, .. } => location,
 204                 _ => continue
 205             };
 206
 207             let init_data = self.initialization_data_at(Location {
 208                 block: bb,
 209                 statement_index: data.statements.len()
 210             });
 211
 212             let path = self.move_data().rev_lookup.find(location);
 213             debug!("collect_drop_flags: {:?}, lv {:?} ({:?})",
 214                    bb, location, path);
 215
 216             let path = match path {
 217                 LookupResult::Exact(e) => e,
 218                 LookupResult::Parent(None) => continue,
 219                 LookupResult::Parent(Some(parent)) => {
 220                     let (_maybe_live, maybe_dead) = init_data.state(parent);
 221                     if maybe_dead {
 222                         span_bug!(terminator.source_info.span,
 223                                   "drop of untracked, uninitialized value {:?}, lv {:?} ({:?})",
 224                                   bb, location, path);
 225                     }
 226                     continue
 227                 }
 228             };
 229
 230             on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
 231                 if self.path_needs_drop(child) {
 232                     let (maybe_live, maybe_dead) = init_data.state(child);
 233                     debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
 234                            child, location, path, (maybe_live, maybe_dead));
 235                     if maybe_live && maybe_dead {
 236                         self.create_drop_flag(child)
 237                     }
 238                 }
 239             });
 240         }
 241     }
 242
 243     fn elaborate_drops(&mut self)
 244     {
 245         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
 246             let loc = Location { block: bb, statement_index: data.statements.len() };
 247             let terminator = data.terminator();
 248
 249             let resume_block = self.patch.resume_block();
 250             match terminator.kind {
 251                 TerminatorKind::Drop { ref location, target, unwind } => {
 252                     let init_data = self.initialization_data_at(loc);
 253                     match self.move_data().rev_lookup.find(location) {
 254                         LookupResult::Exact(path) => {
 255                             self.elaborate_drop(&DropCtxt {
 256                                 source_info: terminator.source_info,
 257                                 is_cleanup: data.is_cleanup,
 258                                 init_data: &init_data,
 259                                 lvalue: location,
 260                                 path: path,
 261                                 succ: target,
 262                                 unwind: if data.is_cleanup {
 263                                     None
 264                                 } else {
 265                                     Some(Option::unwrap_or(unwind, resume_block))
 266                                 }
 267                             }, bb);
 268                         }
 269                         LookupResult::Parent(..) => {
 270                             span_bug!(terminator.source_info.span,
 271                                       "drop of untracked value {:?}", bb);
 272                         }
 273                     }
 274                 }
 275                 TerminatorKind::DropAndReplace { ref location, ref value,
 276                                                  target, unwind } =>
 277                 {
 278                     assert!(!data.is_cleanup);
 279
 280                     self.elaborate_replace(
 281                         loc,
 282                         location, value,
 283                         target, unwind
 284                     );
 285                 }
 286                 _ => continue
 287             }
 288         }
 289     }
 290
 291     /// Elaborate a MIR `replace` terminator. This instruction
 292     /// is not directly handled by translation, and therefore
 293     /// must be desugared.
 294     ///
 295     /// The desugaring drops the location if needed, and then writes
 296     /// the value (including setting the drop flag) over it in *both* arms.
 297     ///
 298     /// The `replace` terminator can also be called on lvalues that
 299     /// are not tracked by elaboration (for example,
 300     /// `replace x[i] <- tmp0`). The borrow checker requires that
 301     /// these locations are initialized before the assignment,
 302     /// so we just generate an unconditional drop.
 303     fn elaborate_replace(
 304         &mut self,
 305         loc: Location,
 306         location: &Lvalue<'tcx>,
 307         value: &Operand<'tcx>,
 308         target: BasicBlock,
 309         unwind: Option<BasicBlock>)
 310     {
 311         let bb = loc.block;
 312         let data = &self.mir[bb];
 313         let terminator = data.terminator();
 314
 315         let assign = Statement {
 316             kind: StatementKind::Assign(location.clone(), Rvalue::Use(value.clone())),
 317             source_info: terminator.source_info
 318         };
 319
 320         let unwind = unwind.unwrap_or(self.patch.resume_block());
 321         let unwind = self.patch.new_block(BasicBlockData {
 322             statements: vec![assign.clone()],
 323             terminator: Some(Terminator {
 324                 kind: TerminatorKind::Goto { target: unwind },
 325                 ..*terminator
 326             }),
 327             is_cleanup: true
 328         });
 329
 330         let target = self.patch.new_block(BasicBlockData {
 331             statements: vec![assign],
 332             terminator: Some(Terminator {
 333                 kind: TerminatorKind::Goto { target: target },
 334                 ..*terminator
 335             }),
 336             is_cleanup: data.is_cleanup,
 337         });
 338
 339         match self.move_data().rev_lookup.find(location) {
 340             LookupResult::Exact(path) => {
 341                 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
 342                 let init_data = self.initialization_data_at(loc);
 343
 344                 self.elaborate_drop(&DropCtxt {
 345                     source_info: terminator.source_info,
 346                     is_cleanup: data.is_cleanup,
 347                     init_data: &init_data,
 348                     lvalue: location,
 349                     path: path,
 350                     succ: target,
 351                     unwind: Some(unwind)
 352                 }, bb);
 353                 on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
 354                     self.set_drop_flag(Location { block: target, statement_index: 0 },
 355                                        child, DropFlagState::Present);
 356                     self.set_drop_flag(Location { block: unwind, statement_index: 0 },
 357                                        child, DropFlagState::Present);
 358                 });
 359             }
 360             LookupResult::Parent(parent) => {
 361                 // drop and replace behind a pointer/array/whatever. The location
 362                 // must be initialized.
 363                 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
 364                 self.patch.patch_terminator(bb, TerminatorKind::Drop {
 365                     location: location.clone(),
 366                     target: target,
 367                     unwind: Some(unwind)
 368                 });
 369             }
 370         }
 371     }
 372
 373     /// This elaborates a single drop instruction, located at `bb`, and
 374     /// patches over it.
 375     ///
 376     /// The elaborated drop checks the drop flags to only drop what
 377     /// is initialized.
 378     ///
 379     /// In addition, the relevant drop flags also need to be cleared
 380     /// to avoid double-drops. However, in the middle of a complex
 381     /// drop, one must avoid clearing some of the flags before they
 382     /// are read, as that would cause a memory leak.
 383     ///
 384     /// In particular, when dropping an ADT, multiple fields may be
 385     /// joined together under the `rest` subpath. They are all controlled
 386     /// by the primary drop flag, but only the last rest-field dropped
 387     /// should clear it (and it must also not clear anything else).
 388     ///
 389     /// FIXME: I think we should just control the flags externally
 390     /// and then we do not need this machinery.
 391     fn elaborate_drop<'a>(&mut self, c: &DropCtxt<'a, 'tcx>, bb: BasicBlock) {
 392         debug!("elaborate_drop({:?})", c);
 393
 394         let mut some_live = false;
 395         let mut some_dead = false;
 396         let mut children_count = 0;
 397         on_all_children_bits(
 398             self.tcx, self.mir, self.move_data(),
 399             c.path, |child| {
 400                 if self.path_needs_drop(child) {
 401                     let (live, dead) = c.init_data.state(child);
 402                     debug!("elaborate_drop: state({:?}) = {:?}",
 403                            child, (live, dead));
 404                     some_live |= live;
 405                     some_dead |= dead;
 406                     children_count += 1;
 407                 }
 408             });
 409
 410         debug!("elaborate_drop({:?}): live - {:?}", c,
 411                (some_live, some_dead));
 412         match (some_live, some_dead) {
 413             (false, false) | (false, true) => {
 414                 // dead drop - patch it out
 415                 self.patch.patch_terminator(bb, TerminatorKind::Goto {
 416                     target: c.succ
 417                 });
 418             }
 419             (true, false) => {
 420                 // static drop - just set the flag
 421                 self.patch.patch_terminator(bb, TerminatorKind::Drop {
 422                     location: c.lvalue.clone(),
 423                     target: c.succ,
 424                     unwind: c.unwind
 425                 });
 426                 self.drop_flags_for_drop(c, bb);
 427             }
 428             (true, true) => {
 429                 // dynamic drop
 430                 let drop_bb = if children_count == 1 || self.must_complete_drop(c) {
 431                     self.conditional_drop(c)
 432                 } else {
 433                     self.open_drop(c)
 434                 };
 435                 self.patch.patch_terminator(bb, TerminatorKind::Goto {
 436                     target: drop_bb
 437                 });
 438             }
 439         }
 440     }
 441
 442     /// Return the lvalue and move path for each field of `variant`,
 443     /// (the move path is `None` if the field is a rest field).
 444     fn move_paths_for_fields(&self,
 445                              base_lv: &Lvalue<'tcx>,
 446                              variant_path: MovePathIndex,
 447                              variant: &'tcx ty::VariantDef,
 448                              substs: &'tcx Substs<'tcx>)
 449                              -> Vec<(Lvalue<'tcx>, Option<MovePathIndex>)>
 450     {
 451         variant.fields.iter().enumerate().map(|(i, f)| {
 452             let subpath =
 453                 super::move_path_children_matching(self.move_data(), variant_path, |p| {
 454                     match p {
 455                         &Projection {
 456                             elem: ProjectionElem::Field(idx, _), ..
 457                         } => idx.index() == i,
 458                         _ => false
 459                     }
 460                 });
 461
 462             let field_ty =
 463                 self.tcx.normalize_associated_type_in_env(
 464                     &f.ty(self.tcx, substs),
 465                     self.param_env()
 466                 );
 467             (base_lv.clone().field(Field::new(i), field_ty), subpath)
 468         }).collect()
 469     }
 470
 471     /// Create one-half of the drop ladder for a list of fields, and return
 472     /// the list of steps in it in reverse order.
 473     ///
 474     /// `unwind_ladder` is such a list of steps in reverse order,
 475     /// which is called instead of the next step if the drop unwinds
 476     /// (the first field is never reached). If it is `None`, all
 477     /// unwind targets are left blank.
 478     fn drop_halfladder<'a>(&mut self,
 479                            c: &DropCtxt<'a, 'tcx>,
 480                            unwind_ladder: Option<Vec<BasicBlock>>,
 481                            succ: BasicBlock,
 482                            fields: &[(Lvalue<'tcx>, Option<MovePathIndex>)],
 483                            is_cleanup: bool)
 484                            -> Vec<BasicBlock>
 485     {
 486         let mut unwind_succ = if is_cleanup {
 487             None
 488         } else {
 489             c.unwind
 490         };
 491
 492         let mut succ = self.new_block(
 493             c, c.is_cleanup, TerminatorKind::Goto { target: succ }
 494         );
 495
 496         // Always clear the "master" drop flag at the bottom of the
 497         // ladder. This is needed because the "master" drop flag
 498         // protects the ADT's discriminant, which is invalidated
 499         // after the ADT is dropped.
 500         self.set_drop_flag(
 501             Location { block: succ, statement_index: 0 },
 502             c.path,
 503             DropFlagState::Absent
 504         );
 505
 506         fields.iter().rev().enumerate().map(|(i, &(ref lv, path))| {
 507             succ = if let Some(path) = path {
 508                 debug!("drop_ladder: for std field {} ({:?})", i, lv);
 509
 510                 self.elaborated_drop_block(&DropCtxt {
 511                     source_info: c.source_info,
 512                     is_cleanup: is_cleanup,
 513                     init_data: c.init_data,
 514                     lvalue: lv,
 515                     path: path,
 516                     succ: succ,
 517                     unwind: unwind_succ,
 518                 })
 519             } else {
 520                 debug!("drop_ladder: for rest field {} ({:?})", i, lv);
 521
 522                 self.complete_drop(&DropCtxt {
 523                     source_info: c.source_info,
 524                     is_cleanup: is_cleanup,
 525                     init_data: c.init_data,
 526                     lvalue: lv,
 527                     path: c.path,
 528                     succ: succ,
 529                     unwind: unwind_succ,
 530                 }, false)
 531             };
 532
 533             unwind_succ = unwind_ladder.as_ref().map(|p| p[i]);
 534             succ
 535         }).collect()
 536     }
 537
 538     /// Create a full drop ladder, consisting of 2 connected half-drop-ladders
 539     ///
 540     /// For example, with 3 fields, the drop ladder is
 541     ///
 542     /// .d0:
 543     ///     ELAB(drop location.0 [target=.d1, unwind=.c1])
 544     /// .d1:
 545     ///     ELAB(drop location.1 [target=.d2, unwind=.c2])
 546     /// .d2:
 547     ///     ELAB(drop location.2 [target=`c.succ`, unwind=`c.unwind`])
 548     /// .c1:
 549     ///     ELAB(drop location.1 [target=.c2])
 550     /// .c2:
 551     ///     ELAB(drop location.2 [target=`c.unwind])
 552     fn drop_ladder<'a>(&mut self,
 553                        c: &DropCtxt<'a, 'tcx>,
 554                        fields: Vec<(Lvalue<'tcx>, Option<MovePathIndex>)>)
 555                        -> BasicBlock
 556     {
 557         debug!("drop_ladder({:?}, {:?})", c, fields);
 558
 559         let mut fields = fields;
 560         fields.retain(|&(ref lvalue, _)| {
 561             let ty = lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
 562             self.tcx.type_needs_drop_given_env(ty, self.param_env())
 563         });
 564
 565         debug!("drop_ladder - fields needing drop: {:?}", fields);
 566
 567         let unwind_ladder = if c.is_cleanup {
 568             None
 569         } else {
 570             Some(self.drop_halfladder(c, None, c.unwind.unwrap(), &fields, true))
 571         };
 572
 573         self.drop_halfladder(c, unwind_ladder, c.succ, &fields, c.is_cleanup)
 574             .last().cloned().unwrap_or(c.succ)
 575     }
 576
 577     fn open_drop_for_tuple<'a>(&mut self, c: &DropCtxt<'a, 'tcx>, tys: &[Ty<'tcx>])
 578                                -> BasicBlock
 579     {
 580         debug!("open_drop_for_tuple({:?}, {:?})", c, tys);
 581
 582         let fields = tys.iter().enumerate().map(|(i, &ty)| {
 583             (c.lvalue.clone().field(Field::new(i), ty),
 584              super::move_path_children_matching(
 585                  self.move_data(), c.path, |proj| match proj {
 586                      &Projection {
 587                          elem: ProjectionElem::Field(f, _), ..
 588                      } => f.index() == i,
 589                      _ => false
 590                  }
 591             ))
 592         }).collect();
 593
 594         self.drop_ladder(c, fields)
 595     }
 596
 597     fn open_drop_for_box<'a>(&mut self, c: &DropCtxt<'a, 'tcx>, ty: Ty<'tcx>)
 598                              -> BasicBlock
 599     {
 600         debug!("open_drop_for_box({:?}, {:?})", c, ty);
 601
 602         let interior_path = super::move_path_children_matching(
 603             self.move_data(), c.path, |proj| match proj {
 604                 &Projection { elem: ProjectionElem::Deref, .. } => true,
 605                 _ => false
 606             }).unwrap();
 607
 608         let interior = c.lvalue.clone().deref();
 609         let inner_c = DropCtxt {
 610             lvalue: &interior,
 611             unwind: c.unwind.map(|u| {
 612                 self.box_free_block(c, ty, u, true)
 613             }),
 614             succ: self.box_free_block(c, ty, c.succ, c.is_cleanup),
 615             path: interior_path,
 616             ..*c
 617         };
 618
 619         self.elaborated_drop_block(&inner_c)
 620     }
 621
 622     fn open_drop_for_variant<'a>(&mut self,
 623                                  c: &DropCtxt<'a, 'tcx>,
 624                                  drop_block: &mut Option<BasicBlock>,
 625                                  adt: &'tcx ty::AdtDef,
 626                                  substs: &'tcx Substs<'tcx>,
 627                                  variant_index: usize)
 628                                  -> BasicBlock
 629     {
 630         let subpath = super::move_path_children_matching(
 631             self.move_data(), c.path, |proj| match proj {
 632                 &Projection {
 633                     elem: ProjectionElem::Downcast(_, idx), ..
 634                 } => idx == variant_index,
 635                 _ => false
 636             });
 637
 638         if let Some(variant_path) = subpath {
 639             let base_lv = c.lvalue.clone().elem(
 640                 ProjectionElem::Downcast(adt, variant_index)
 641             );
 642             let fields = self.move_paths_for_fields(
 643                 &base_lv,
 644                 variant_path,
 645                 &adt.variants[variant_index],
 646                 substs);
 647             self.drop_ladder(c, fields)
 648         } else {
 649             // variant not found - drop the entire enum
 650             if let None = *drop_block {
 651                 *drop_block = Some(self.complete_drop(c, true));
 652             }
 653             return drop_block.unwrap();
 654         }
 655     }
 656
 657     fn open_drop_for_adt<'a>(&mut self, c: &DropCtxt<'a, 'tcx>,
 658                              adt: &'tcx ty::AdtDef, substs: &'tcx Substs<'tcx>)
 659                              -> BasicBlock {
 660         debug!("open_drop_for_adt({:?}, {:?}, {:?})", c, adt, substs);
 661
 662         let mut drop_block = None;
 663
 664         match adt.variants.len() {
 665             1 => {
 666                 let fields = self.move_paths_for_fields(
 667                     c.lvalue,
 668                     c.path,
 669                     &adt.variants[0],
 670                     substs
 671                 );
 672                 self.drop_ladder(c, fields)
 673             }
 674             _ => {
 675                 let variant_drops : Vec<BasicBlock> =
 676                     (0..adt.variants.len()).map(|i| {
 677                         self.open_drop_for_variant(c, &mut drop_block,
 678                                                    adt, substs, i)
 679                     }).collect();
 680
 681                 // If there are multiple variants, then if something
 682                 // is present within the enum the discriminant, tracked
 683                 // by the rest path, must be initialized.
 684                 //
 685                 // Additionally, we do not want to switch on the
 686                 // discriminant after it is free-ed, because that
 687                 // way lies only trouble.
 688
 689                 let switch_block = self.new_block(
 690                     c, c.is_cleanup, TerminatorKind::Switch {
 691                         discr: c.lvalue.clone(),
 692                         adt_def: adt,
 693                         targets: variant_drops
 694                     });
 695
 696                 self.drop_flag_test_block(c, switch_block)
 697             }
 698         }
 699     }
 700
 701     /// The slow-path - create an "open", elaborated drop for a type
 702     /// which is moved-out-of only partially, and patch `bb` to a jump
 703     /// to it. This must not be called on ADTs with a destructor,
 704     /// as these can't be moved-out-of, except for `Box<T>`, which is
 705     /// special-cased.
 706     ///
 707     /// This creates a "drop ladder" that drops the needed fields of the
 708     /// ADT, both in the success case or if one of the destructors fail.
 709     fn open_drop<'a>(&mut self, c: &DropCtxt<'a, 'tcx>) -> BasicBlock {
 710         let ty = c.lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
 711         match ty.sty {
 712             ty::TyClosure(def_id, substs) => {
 713                 let tys : Vec<_> = substs.upvar_tys(def_id, self.tcx).collect();
 714                 self.open_drop_for_tuple(c, &tys)
 715             }
 716             ty::TyTuple(tys, _) => {
 717                 self.open_drop_for_tuple(c, tys)
 718             }
 719             ty::TyAdt(def, _) if def.is_box() => {
 720                 self.open_drop_for_box(c, ty.boxed_ty())
 721             }
 722             ty::TyAdt(def, substs) => {
 723                 self.open_drop_for_adt(c, def, substs)
 724             }
 725             _ => bug!("open drop from non-ADT `{:?}`", ty)
 726         }
 727     }
 728
 729     /// Return a basic block that drop an lvalue using the context
 730     /// and path in `c`. If `update_drop_flag` is true, also
 731     /// clear `c`.
 732     ///
 733     /// if FLAG(c.path)
 734     ///     if(update_drop_flag) FLAG(c.path) = false
 735     ///     drop(c.lv)
 736     fn complete_drop<'a>(
 737         &mut self,
 738         c: &DropCtxt<'a, 'tcx>,
 739         update_drop_flag: bool)
 740         -> BasicBlock
 741     {
 742         debug!("complete_drop({:?},{:?})", c, update_drop_flag);
 743
 744         let drop_block = self.drop_block(c);
 745         if update_drop_flag {
 746             self.set_drop_flag(
 747                 Location { block: drop_block, statement_index: 0 },
 748                 c.path,
 749                 DropFlagState::Absent
 750             );
 751         }
 752
 753         self.drop_flag_test_block(c, drop_block)
 754     }
 755
 756     /// Create a simple conditional drop.
 757     ///
 758     /// if FLAG(c.lv)
 759     ///     FLAGS(c.lv) = false
 760     ///     drop(c.lv)
 761     fn conditional_drop<'a>(&mut self, c: &DropCtxt<'a, 'tcx>)
 762                             -> BasicBlock
 763     {
 764         debug!("conditional_drop({:?})", c);
 765         let drop_bb = self.drop_block(c);
 766         self.drop_flags_for_drop(c, drop_bb);
 767
 768         self.drop_flag_test_block(c, drop_bb)
 769     }
 770
 771     fn new_block<'a>(&mut self,
 772                      c: &DropCtxt<'a, 'tcx>,
 773                      is_cleanup: bool,
 774                      k: TerminatorKind<'tcx>)
 775                      -> BasicBlock
 776     {
 777         self.patch.new_block(BasicBlockData {
 778             statements: vec![],
 779             terminator: Some(Terminator {
 780                 source_info: c.source_info, kind: k
 781             }),
 782             is_cleanup: is_cleanup
 783         })
 784     }
 785
 786     fn elaborated_drop_block<'a>(&mut self, c: &DropCtxt<'a, 'tcx>) -> BasicBlock {
 787         debug!("elaborated_drop_block({:?})", c);
 788         let blk = self.drop_block(c);
 789         self.elaborate_drop(c, blk);
 790         blk
 791     }
 792
 793     fn drop_flag_test_block<'a>(&mut self,
 794                                 c: &DropCtxt<'a, 'tcx>,
 795                                 on_set: BasicBlock)
 796                                 -> BasicBlock {
 797         self.drop_flag_test_block_with_succ(c, c.is_cleanup, on_set, c.succ)
 798     }
 799
 800     fn drop_flag_test_block_with_succ<'a>(&mut self,
 801                                           c: &DropCtxt<'a, 'tcx>,
 802                                           is_cleanup: bool,
 803                                           on_set: BasicBlock,
 804                                           on_unset: BasicBlock)
 805                                           -> BasicBlock
 806     {
 807         let (maybe_live, maybe_dead) = c.init_data.state(c.path);
 808         debug!("drop_flag_test_block({:?},{:?},{:?}) - {:?}",
 809                c, is_cleanup, on_set, (maybe_live, maybe_dead));
 810
 811         match (maybe_live, maybe_dead) {
 812             (false, _) => on_unset,
 813             (true, false) => on_set,
 814             (true, true) => {
 815                 let flag = self.drop_flag(c.path).unwrap();
 816                 self.new_block(c, is_cleanup, TerminatorKind::If {
 817                     cond: Operand::Consume(flag),
 818                     targets: (on_set, on_unset)
 819                 })
 820             }
 821         }
 822     }
 823
 824     fn drop_block<'a>(&mut self, c: &DropCtxt<'a, 'tcx>) -> BasicBlock {
 825         self.new_block(c, c.is_cleanup, TerminatorKind::Drop {
 826             location: c.lvalue.clone(),
 827             target: c.succ,
 828             unwind: c.unwind
 829         })
 830     }
 831
 832     fn box_free_block<'a>(
 833         &mut self,
 834         c: &DropCtxt<'a, 'tcx>,
 835         ty: Ty<'tcx>,
 836         target: BasicBlock,
 837         is_cleanup: bool
 838     ) -> BasicBlock {
 839         let block = self.unelaborated_free_block(c, ty, target, is_cleanup);
 840         self.drop_flag_test_block_with_succ(c, is_cleanup, block, target)
 841     }
 842
 843     fn unelaborated_free_block<'a>(
 844         &mut self,
 845         c: &DropCtxt<'a, 'tcx>,
 846         ty: Ty<'tcx>,
 847         target: BasicBlock,
 848         is_cleanup: bool
 849     ) -> BasicBlock {
 850         let mut statements = vec![];
 851         if let Some(&flag) = self.drop_flags.get(&c.path) {
 852             statements.push(Statement {
 853                 source_info: c.source_info,
 854                 kind: StatementKind::Assign(
 855                     Lvalue::Local(flag),
 856                     self.constant_bool(c.source_info.span, false)
 857                 )
 858             });
 859         }
 860
 861         let tcx = self.tcx;
 862         let unit_temp = Lvalue::Local(self.patch.new_temp(tcx.mk_nil()));
 863         let free_func = tcx.require_lang_item(lang_items::BoxFreeFnLangItem);
 864         let substs = tcx.mk_substs(iter::once(Kind::from(ty)));
 865         let fty = tcx.item_type(free_func).subst(tcx, substs);
 866
 867         self.patch.new_block(BasicBlockData {
 868             statements: statements,
 869             terminator: Some(Terminator {
 870                 source_info: c.source_info, kind: TerminatorKind::Call {
 871                     func: Operand::Constant(Constant {
 872                         span: c.source_info.span,
 873                         ty: fty,
 874                         literal: Literal::Item {
 875                             def_id: free_func,
 876                             substs: substs
 877                         }
 878                     }),
 879                     args: vec![Operand::Consume(c.lvalue.clone())],
 880                     destination: Some((unit_temp, target)),
 881                     cleanup: None
 882                 }
 883             }),
 884             is_cleanup: is_cleanup
 885         })
 886     }
 887
 888     fn must_complete_drop<'a>(&self, c: &DropCtxt<'a, 'tcx>) -> bool {
 889         // if we have a destuctor, we must *not* split the drop.
 890
 891         // dataflow can create unneeded children in some cases
 892         // - be sure to ignore them.
 893
 894         let ty = c.lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
 895
 896         match ty.sty {
 897             ty::TyAdt(def, _) => {
 898                 if def.has_dtor() && !def.is_box() {
 899                     self.tcx.sess.span_warn(
 900                         c.source_info.span,
 901                         &format!("dataflow bug??? moving out of type with dtor {:?}",
 902                                  c));
 903                     true
 904                 } else {
 905                     false
 906                 }
 907             }
 908             _ => false
 909         }
 910     }
 911
 912     fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
 913         Rvalue::Use(Operand::Constant(Constant {
 914             span: span,
 915             ty: self.tcx.types.bool,
 916             literal: Literal::Value { value: ConstVal::Bool(val) }
 917         }))
 918     }
 919
 920     fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
 921         if let Some(&flag) = self.drop_flags.get(&path) {
 922             let span = self.patch.source_info_for_location(self.mir, loc).span;
 923             let val = self.constant_bool(span, val.value());
 924             self.patch.add_assign(loc, Lvalue::Local(flag), val);
 925         }
 926     }
 927
 928     fn drop_flags_on_init(&mut self) {
 929         let loc = Location { block: START_BLOCK, statement_index: 0 };
 930         let span = self.patch.source_info_for_location(self.mir, loc).span;
 931         let false_ = self.constant_bool(span, false);
 932         for flag in self.drop_flags.values() {
 933             self.patch.add_assign(loc, Lvalue::Local(*flag), false_.clone());
 934         }
 935     }
 936
 937     fn drop_flags_for_fn_rets(&mut self) {
 938         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
 939             if let TerminatorKind::Call {
 940                 destination: Some((ref lv, tgt)), cleanup: Some(_), ..
 941             } = data.terminator().kind {
 942                 assert!(!self.patch.is_patched(bb));
 943
 944                 let loc = Location { block: tgt, statement_index: 0 };
 945                 let path = self.move_data().rev_lookup.find(lv);
 946                 on_lookup_result_bits(
 947                     self.tcx, self.mir, self.move_data(), path,
 948                     |child| self.set_drop_flag(loc, child, DropFlagState::Present)
 949                 );
 950             }
 951         }
 952     }
 953
 954     fn drop_flags_for_args(&mut self) {
 955         let loc = Location { block: START_BLOCK, statement_index: 0 };
 956         super::drop_flag_effects_for_function_entry(
 957             self.tcx, self.mir, self.env, |path, ds| {
 958                 self.set_drop_flag(loc, path, ds);
 959             }
 960         )
 961     }
 962
 963     fn drop_flags_for_locs(&mut self) {
 964         // We intentionally iterate only over the *old* basic blocks.
 965         //
 966         // Basic blocks created by drop elaboration update their
 967         // drop flags by themselves, to avoid the drop flags being
 968         // clobbered before they are read.
 969
 970         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
 971             debug!("drop_flags_for_locs({:?})", data);
 972             for i in 0..(data.statements.len()+1) {
 973                 debug!("drop_flag_for_locs: stmt {}", i);
 974                 let mut allow_initializations = true;
 975                 if i == data.statements.len() {
 976                     match data.terminator().kind {
 977                         TerminatorKind::Drop { .. } => {
 978                             // drop elaboration should handle that by itself
 979                             continue
 980                         }
 981                         TerminatorKind::DropAndReplace { .. } => {
 982                             // this contains the move of the source and
 983                             // the initialization of the destination. We
 984                             // only want the former - the latter is handled
 985                             // by the elaboration code and must be done
 986                             // *after* the destination is dropped.
 987                             assert!(self.patch.is_patched(bb));
 988                             allow_initializations = false;
 989                         }
 990                         _ => {
 991                             assert!(!self.patch.is_patched(bb));
 992                         }
 993                     }
 994                 }
 995                 let loc = Location { block: bb, statement_index: i };
 996                 super::drop_flag_effects_for_location(
 997                     self.tcx, self.mir, self.env, loc, |path, ds| {
 998                         if ds == DropFlagState::Absent || allow_initializations {
 999                             self.set_drop_flag(loc, path, ds)
1000                         }
1001                     }
1002                 )
1003             }
1004
1005             // There may be a critical edge after this call,
1006             // so mark the return as initialized *before* the
1007             // call.
1008             if let TerminatorKind::Call {
1009                 destination: Some((ref lv, _)), cleanup: None, ..
1010             } = data.terminator().kind {
1011                 assert!(!self.patch.is_patched(bb));
1012
1013                 let loc = Location { block: bb, statement_index: data.statements.len() };
1014                 let path = self.move_data().rev_lookup.find(lv);
1015                 on_lookup_result_bits(
1016                     self.tcx, self.mir, self.move_data(), path,
1017                     |child| self.set_drop_flag(loc, child, DropFlagState::Present)
1018                 );
1019             }
1020         }
1021     }
1022
1023     fn drop_flags_for_drop<'a>(&mut self,
1024                                c: &DropCtxt<'a, 'tcx>,
1025                                bb: BasicBlock)
1026     {
1027         let loc = self.patch.terminator_loc(self.mir, bb);
1028         on_all_children_bits(
1029             self.tcx, self.mir, self.move_data(), c.path,
1030             |child| self.set_drop_flag(loc, child, DropFlagState::Absent)
1031         );
1032     }
1033 }