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