src/librustc_mir/borrow_check.rs

   1 // Copyright 2017 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 //! This query borrow-checks the MIR to (further) ensure it is not broken.
  12
  13 use rustc::hir::def_id::{DefId};
  14 use rustc::infer::{InferCtxt};
  15 use rustc::ty::{self, TyCtxt, ParamEnv};
  16 use rustc::ty::maps::Providers;
  17 use rustc::mir::{AssertMessage, BasicBlock, BorrowKind, Location, Lvalue};
  18 use rustc::mir::{Mir, Mutability, Operand, Projection, ProjectionElem, Rvalue};
  19 use rustc::mir::{Statement, StatementKind, Terminator, TerminatorKind};
  20 use rustc::mir::transform::{MirSource};
  21
  22 use rustc_data_structures::indexed_set::{self, IdxSetBuf};
  23 use rustc_data_structures::indexed_vec::{Idx};
  24
  25 use syntax::ast::{self};
  26 use syntax_pos::{DUMMY_SP, Span};
  27
  28 use dataflow::{do_dataflow};
  29 use dataflow::{MoveDataParamEnv};
  30 use dataflow::{BitDenotation, BlockSets, DataflowResults, DataflowResultsConsumer};
  31 use dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
  32 use dataflow::{Borrows, BorrowData, BorrowIndex};
  33 use dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex, LookupResult};
  34 use util::borrowck_errors::{BorrowckErrors, Origin};
  35
  36 use self::MutateMode::{JustWrite, WriteAndRead};
  37 use self::ConsumeKind::{Consume};
  38
  39
  40 pub fn provide(providers: &mut Providers) {
  41     *providers = Providers {
  42         mir_borrowck,
  43         ..*providers
  44     };
  45 }
  46
  47 fn mir_borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) {
  48     let mir = tcx.mir_validated(def_id);
  49     let src = MirSource::from_local_def_id(tcx, def_id);
  50     debug!("run query mir_borrowck: {}", tcx.node_path_str(src.item_id()));
  51
  52     let mir: &Mir<'tcx> = &mir.borrow();
  53     if !tcx.has_attr(def_id, "rustc_mir_borrowck") && !tcx.sess.opts.debugging_opts.borrowck_mir {
  54         return;
  55     }
  56
  57     let id = src.item_id();
  58     let attributes = tcx.get_attrs(def_id);
  59     let param_env = tcx.param_env(def_id);
  60     tcx.infer_ctxt().enter(|_infcx| {
  61
  62         let move_data = MoveData::gather_moves(mir, tcx, param_env);
  63         let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env };
  64         let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
  65         let flow_borrows = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
  66                                        Borrows::new(tcx, mir),
  67                                        |bd, i| bd.location(i));
  68         let flow_inits = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
  69                                      MaybeInitializedLvals::new(tcx, mir, &mdpe),
  70                                      |bd, i| &bd.move_data().move_paths[i]);
  71         let flow_uninits = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
  72                                        MaybeUninitializedLvals::new(tcx, mir, &mdpe),
  73                                        |bd, i| &bd.move_data().move_paths[i]);
  74
  75         let mut mbcx = MirBorrowckCtxt {
  76             tcx: tcx,
  77             mir: mir,
  78             node_id: id,
  79             move_data: &mdpe.move_data,
  80             param_env: param_env,
  81             fake_infer_ctxt: &_infcx,
  82         };
  83
  84         let mut state = InProgress::new(flow_borrows,
  85                                         flow_inits,
  86                                         flow_uninits);
  87
  88         mbcx.analyze_results(&mut state); // entry point for DataflowResultsConsumer
  89     });
  90
  91     debug!("mir_borrowck done");
  92 }
  93
  94 #[allow(dead_code)]
  95 pub struct MirBorrowckCtxt<'c, 'b, 'a: 'b+'c, 'gcx: 'a+'tcx, 'tcx: 'a> {
  96     tcx: TyCtxt<'a, 'gcx, 'gcx>,
  97     mir: &'b Mir<'gcx>,
  98     node_id: ast::NodeId,
  99     move_data: &'b MoveData<'gcx>,
 100     param_env: ParamEnv<'tcx>,
 101     fake_infer_ctxt: &'c InferCtxt<'c, 'gcx, 'tcx>,
 102 }
 103
 104 // (forced to be `pub` due to its use as an associated type below.)
 105 pub struct InProgress<'b, 'tcx: 'b> {
 106     borrows: FlowInProgress<Borrows<'b, 'tcx>>,
 107     inits: FlowInProgress<MaybeInitializedLvals<'b, 'tcx>>,
 108     uninits: FlowInProgress<MaybeUninitializedLvals<'b, 'tcx>>,
 109 }
 110
 111 struct FlowInProgress<BD> where BD: BitDenotation {
 112     base_results: DataflowResults<BD>,
 113     curr_state: IdxSetBuf<BD::Idx>,
 114     stmt_gen: IdxSetBuf<BD::Idx>,
 115     stmt_kill: IdxSetBuf<BD::Idx>,
 116 }
 117
 118 // Check that:
 119 // 1. assignments are always made to mutable locations (FIXME: does that still really go here?)
 120 // 2. loans made in overlapping scopes do not conflict
 121 // 3. assignments do not affect things loaned out as immutable
 122 // 4. moves do not affect things loaned out in any way
 123 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> DataflowResultsConsumer<'b, 'gcx>
 124     for MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
 125 {
 126     type FlowState = InProgress<'b, 'gcx>;
 127
 128     fn mir(&self) -> &'b Mir<'gcx> { self.mir }
 129
 130     fn reset_to_entry_of(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
 131         flow_state.each_flow(|b| b.reset_to_entry_of(bb),
 132                              |i| i.reset_to_entry_of(bb),
 133                              |u| u.reset_to_entry_of(bb));
 134     }
 135
 136     fn reconstruct_statement_effect(&mut self,
 137                                     location: Location,
 138                                     flow_state: &mut Self::FlowState) {
 139         flow_state.each_flow(|b| b.reconstruct_statement_effect(location),
 140                              |i| i.reconstruct_statement_effect(location),
 141                              |u| u.reconstruct_statement_effect(location));
 142     }
 143
 144     fn apply_local_effect(&mut self,
 145                           _location: Location,
 146                           flow_state: &mut Self::FlowState) {
 147         flow_state.each_flow(|b| b.apply_local_effect(),
 148                              |i| i.apply_local_effect(),
 149                              |u| u.apply_local_effect());
 150     }
 151
 152     fn reconstruct_terminator_effect(&mut self,
 153                                      location: Location,
 154                                      flow_state: &mut Self::FlowState) {
 155         flow_state.each_flow(|b| b.reconstruct_terminator_effect(location),
 156                              |i| i.reconstruct_terminator_effect(location),
 157                              |u| u.reconstruct_terminator_effect(location));
 158     }
 159
 160     fn visit_block_entry(&mut self,
 161                          bb: BasicBlock,
 162                          flow_state: &Self::FlowState) {
 163         let summary = flow_state.summary();
 164         debug!("MirBorrowckCtxt::process_block({:?}): {}", bb, summary);
 165     }
 166
 167     fn visit_statement_entry(&mut self,
 168                              location: Location,
 169                              stmt: &Statement<'gcx>,
 170                              flow_state: &Self::FlowState) {
 171         let summary = flow_state.summary();
 172         debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {}", location, stmt, summary);
 173         let span = stmt.source_info.span;
 174         match stmt.kind {
 175             StatementKind::Assign(ref lhs, ref rhs) => {
 176                 self.mutate_lvalue(ContextKind::AssignLhs.new(location),
 177                                    (lhs, span), JustWrite, flow_state);
 178                 self.consume_rvalue(ContextKind::AssignRhs.new(location),
 179                                     (rhs, span), location, flow_state);
 180             }
 181             StatementKind::SetDiscriminant { ref lvalue, variant_index: _ } => {
 182                 self.mutate_lvalue(ContextKind::SetDiscrim.new(location),
 183                                    (lvalue, span), JustWrite, flow_state);
 184             }
 185             StatementKind::InlineAsm { ref asm, ref outputs, ref inputs } => {
 186                 for (o, output) in asm.outputs.iter().zip(outputs) {
 187                     if o.is_indirect {
 188                         self.consume_lvalue(ContextKind::InlineAsm.new(location),
 189                                             Consume,
 190                                             (output, span),
 191                                             flow_state);
 192                     } else {
 193                         self.mutate_lvalue(ContextKind::InlineAsm.new(location),
 194                                            (output, span),
 195                                            if o.is_rw { WriteAndRead } else { JustWrite },
 196                                            flow_state);
 197                     }
 198                 }
 199                 for input in inputs {
 200                     self.consume_operand(ContextKind::InlineAsm.new(location),
 201                                          Consume,
 202                                          (input, span), flow_state);
 203                 }
 204             }
 205             StatementKind::EndRegion(ref _rgn) => {
 206                 // ignored when consuming results (update to
 207                 // flow_state already handled).
 208             }
 209             StatementKind::Nop |
 210             StatementKind::Validate(..) |
 211             StatementKind::StorageLive(..) => {
 212                 // ignored by borrowck
 213             }
 214
 215             StatementKind::StorageDead(ref lvalue) => {
 216                 // causes non-drop values to be dropped.
 217                 self.consume_lvalue(ContextKind::StorageDead.new(location),
 218                                     ConsumeKind::Consume,
 219                                     (lvalue, span),
 220                                     flow_state)
 221             }
 222         }
 223     }
 224
 225     fn visit_terminator_entry(&mut self,
 226                               location: Location,
 227                               term: &Terminator<'gcx>,
 228                               flow_state: &Self::FlowState) {
 229         let loc = location;
 230         let summary = flow_state.summary();
 231         debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {}", location, term, summary);
 232         let span = term.source_info.span;
 233         match term.kind {
 234             TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => {
 235                 self.consume_operand(ContextKind::SwitchInt.new(loc),
 236                                      Consume,
 237                                      (discr, span), flow_state);
 238             }
 239             TerminatorKind::Drop { location: ref drop_lvalue, target: _, unwind: _ } => {
 240                 self.consume_lvalue(ContextKind::Drop.new(loc),
 241                                     ConsumeKind::Drop,
 242                                     (drop_lvalue, span), flow_state);
 243             }
 244             TerminatorKind::DropAndReplace { location: ref drop_lvalue,
 245                                              value: ref new_value,
 246                                              target: _,
 247                                              unwind: _ } => {
 248                 self.mutate_lvalue(ContextKind::DropAndReplace.new(loc),
 249                                    (drop_lvalue, span), JustWrite, flow_state);
 250                 self.consume_operand(ContextKind::DropAndReplace.new(loc),
 251                                      ConsumeKind::Drop,
 252                                      (new_value, span), flow_state);
 253             }
 254             TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => {
 255                 self.consume_operand(ContextKind::CallOperator.new(loc),
 256                                      Consume,
 257                                      (func, span), flow_state);
 258                 for arg in args {
 259                     self.consume_operand(ContextKind::CallOperand.new(loc),
 260                                          Consume,
 261                                          (arg, span), flow_state);
 262                 }
 263                 if let Some((ref dest, _/*bb*/)) = *destination {
 264                     self.mutate_lvalue(ContextKind::CallDest.new(loc),
 265                                        (dest, span), JustWrite, flow_state);
 266                 }
 267             }
 268             TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
 269                 self.consume_operand(ContextKind::Assert.new(loc),
 270                                      Consume,
 271                                      (cond, span), flow_state);
 272                 match *msg {
 273                     AssertMessage::BoundsCheck { ref len, ref index } => {
 274                         self.consume_operand(ContextKind::Assert.new(loc),
 275                                              Consume,
 276                                              (len, span), flow_state);
 277                         self.consume_operand(ContextKind::Assert.new(loc),
 278                                              Consume,
 279                                              (index, span), flow_state);
 280                     }
 281                     AssertMessage::Math(_/*const_math_err*/) => {}
 282                 }
 283             }
 284
 285             TerminatorKind::Goto { target: _ } |
 286             TerminatorKind::Resume |
 287             TerminatorKind::Return |
 288             TerminatorKind::Unreachable => {
 289                 // no data used, thus irrelevant to borrowck
 290             }
 291         }
 292     }
 293 }
 294
 295 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 296 enum MutateMode { JustWrite, WriteAndRead }
 297
 298 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 299 enum ConsumeKind { Drop, Consume }
 300
 301 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 302 enum Control { Continue, Break }
 303
 304 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 305     fn mutate_lvalue(&mut self,
 306                      context: Context,
 307                      lvalue_span: (&Lvalue<'gcx>, Span),
 308                      mode: MutateMode,
 309                      flow_state: &InProgress<'b, 'gcx>) {
 310         // Write of P[i] or *P, or WriteAndRead of any P, requires P init'd.
 311         match mode {
 312             MutateMode::WriteAndRead => {
 313                 self.check_if_path_is_moved(context, lvalue_span, flow_state);
 314             }
 315             MutateMode::JustWrite => {
 316                 self.check_if_assigned_path_is_moved(context, lvalue_span, flow_state);
 317             }
 318         }
 319
 320         // check we don't invalidate any outstanding loans
 321         self.each_borrow_involving_path(context,
 322                                         lvalue_span.0, flow_state, |this, _index, _data| {
 323                                             this.report_illegal_mutation_of_borrowed(context,
 324                                                                                      lvalue_span);
 325                                             Control::Break
 326                                         });
 327
 328         // check for reassignments to immutable local variables
 329         self.check_if_reassignment_to_immutable_state(context, lvalue_span, flow_state);
 330     }
 331
 332     fn consume_rvalue(&mut self,
 333                       context: Context,
 334                       (rvalue, span): (&Rvalue<'gcx>, Span),
 335                       location: Location,
 336                       flow_state: &InProgress<'b, 'gcx>) {
 337         match *rvalue {
 338             Rvalue::Ref(_/*rgn*/, bk, ref lvalue) => {
 339                 self.borrow(context, location, bk, (lvalue, span), flow_state)
 340             }
 341
 342             Rvalue::Use(ref operand) |
 343             Rvalue::Repeat(ref operand, _) |
 344             Rvalue::UnaryOp(_/*un_op*/, ref operand) |
 345             Rvalue::Cast(_/*cast_kind*/, ref operand, _/*ty*/) => {
 346                 self.consume_operand(context, Consume, (operand, span), flow_state)
 347             }
 348
 349             Rvalue::Len(ref lvalue) |
 350             Rvalue::Discriminant(ref lvalue) => {
 351                 // len(_)/discriminant(_) merely read, not consume.
 352                 self.check_if_path_is_moved(context, (lvalue, span), flow_state);
 353             }
 354
 355             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2) |
 356             Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
 357                 self.consume_operand(context, Consume, (operand1, span), flow_state);
 358                 self.consume_operand(context, Consume, (operand2, span), flow_state);
 359             }
 360
 361             Rvalue::NullaryOp(_op, _ty) => {
 362                 // nullary ops take no dynamic input; no borrowck effect.
 363                 //
 364                 // FIXME: is above actually true? Do we want to track
 365                 // the fact that uninitialized data can be created via
 366                 // `NullOp::Box`?
 367             }
 368
 369             Rvalue::Aggregate(ref _aggregate_kind, ref operands) => {
 370                 for operand in operands {
 371                     self.consume_operand(context, Consume, (operand, span), flow_state);
 372                 }
 373             }
 374         }
 375     }
 376
 377     fn consume_operand(&mut self,
 378                        context: Context,
 379                        consume_via_drop: ConsumeKind,
 380                        (operand, span): (&Operand<'gcx>, Span),
 381                        flow_state: &InProgress<'b, 'gcx>) {
 382         match *operand {
 383             Operand::Consume(ref lvalue) =>
 384                 self.consume_lvalue(context, consume_via_drop, (lvalue, span), flow_state),
 385             Operand::Constant(_) => {}
 386         }
 387     }
 388
 389     fn consume_lvalue(&mut self,
 390                       context: Context,
 391                       consume_via_drop: ConsumeKind,
 392                       lvalue_span: (&Lvalue<'gcx>, Span),
 393                       flow_state: &InProgress<'b, 'gcx>) {
 394         let lvalue = lvalue_span.0;
 395         let ty = lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
 396         let moves_by_default =
 397             self.fake_infer_ctxt.type_moves_by_default(self.param_env, ty, DUMMY_SP);
 398         if moves_by_default {
 399             // move of lvalue: check if this is move of already borrowed path
 400             self.each_borrow_involving_path(
 401                 context, lvalue_span.0, flow_state, |this, _idx, borrow| {
 402                     if !borrow.compatible_with(BorrowKind::Mut) {
 403                         this.report_move_out_while_borrowed(context, lvalue_span);
 404                         Control::Break
 405                     } else {
 406                         Control::Continue
 407                     }
 408                 });
 409         } else {
 410             // copy of lvalue: check if this is "copy of frozen path" (FIXME: see check_loans.rs)
 411             self.each_borrow_involving_path(
 412                 context, lvalue_span.0, flow_state, |this, _idx, borrow| {
 413                     if !borrow.compatible_with(BorrowKind::Shared) {
 414                         this.report_use_while_mutably_borrowed(context, lvalue_span);
 415                         Control::Break
 416                     } else {
 417                         Control::Continue
 418                     }
 419                 });
 420         }
 421
 422         // Finally, check if path was already moved.
 423         match consume_via_drop {
 424             ConsumeKind::Drop => {
 425                 // If path is merely being dropped, then we'll already
 426                 // check the drop flag to see if it is moved (thus we
 427                 // skip this check in that case).
 428             }
 429             ConsumeKind::Consume => {
 430                 self.check_if_path_is_moved(context, lvalue_span, flow_state);
 431             }
 432         }
 433     }
 434
 435     fn borrow(&mut self,
 436               context: Context,
 437               location: Location,
 438               bk: BorrowKind,
 439               lvalue_span: (&Lvalue<'gcx>, Span),
 440               flow_state: &InProgress<'b, 'gcx>) {
 441         debug!("borrow location: {:?} lvalue: {:?} span: {:?}",
 442                location, lvalue_span.0, lvalue_span.1);
 443         self.check_if_path_is_moved(context, lvalue_span, flow_state);
 444         self.check_for_conflicting_loans(context, location, bk, lvalue_span, flow_state);
 445     }
 446 }
 447
 448 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 449     fn check_if_reassignment_to_immutable_state(&mut self,
 450                                                 context: Context,
 451                                                 (lvalue, span): (&Lvalue<'gcx>, Span),
 452                                                 flow_state: &InProgress<'b, 'gcx>) {
 453         let move_data = flow_state.inits.base_results.operator().move_data();
 454
 455         // determine if this path has a non-mut owner (and thus needs checking).
 456         let mut l = lvalue;
 457         loop {
 458             match *l {
 459                 Lvalue::Projection(ref proj) => {
 460                     l = &proj.base;
 461                     continue;
 462                 }
 463                 Lvalue::Local(local) => {
 464                     match self.mir.local_decls[local].mutability {
 465                         Mutability::Not => break, // needs check
 466                         Mutability::Mut => return,
 467                     }
 468                 }
 469                 Lvalue::Static(_) => {
 470                     // mutation of non-mut static is always illegal,
 471                     // independent of dataflow.
 472                     self.report_assignment_to_static(context, (lvalue, span));
 473                     return;
 474                 }
 475             }
 476         }
 477
 478         if let Some(mpi) = self.move_path_for_lvalue(context, move_data, lvalue) {
 479             if flow_state.inits.curr_state.contains(&mpi) {
 480                 // may already be assigned before reaching this statement;
 481                 // report error.
 482                 self.report_illegal_reassignment(context, (lvalue, span));
 483             }
 484         }
 485     }
 486
 487     fn check_if_path_is_moved(&mut self,
 488                               context: Context,
 489                               lvalue_span: (&Lvalue<'gcx>, Span),
 490                               flow_state: &InProgress<'b, 'gcx>) {
 491         // FIXME: analogous code in check_loans first maps `lvalue` to
 492         // its base_path ... but is that what we want here?
 493         let lvalue = self.base_path(lvalue_span.0);
 494
 495         let maybe_uninits = &flow_state.uninits;
 496         let move_data = maybe_uninits.base_results.operator().move_data();
 497         if let Some(mpi) = self.move_path_for_lvalue(context, move_data, lvalue) {
 498             if maybe_uninits.curr_state.contains(&mpi) {
 499                 // find and report move(s) that could cause this to be uninitialized
 500                 self.report_use_of_moved(context, lvalue_span);
 501             } else {
 502                 // sanity check: initialized on *some* path, right?
 503                 assert!(flow_state.inits.curr_state.contains(&mpi));
 504             }
 505         }
 506     }
 507
 508     fn move_path_for_lvalue(&mut self,
 509                             _context: Context,
 510                             move_data: &MoveData<'gcx>,
 511                             lvalue: &Lvalue<'gcx>)
 512                             -> Option<MovePathIndex>
 513     {
 514         // If returns None, then there is no move path corresponding
 515         // to a direct owner of `lvalue` (which means there is nothing
 516         // that borrowck tracks for its analysis).
 517
 518         match move_data.rev_lookup.find(lvalue) {
 519             LookupResult::Parent(_) => None,
 520             LookupResult::Exact(mpi) => Some(mpi),
 521         }
 522     }
 523
 524     fn check_if_assigned_path_is_moved(&mut self,
 525                                        context: Context,
 526                                        (lvalue, span): (&Lvalue<'gcx>, Span),
 527                                        flow_state: &InProgress<'b, 'gcx>) {
 528         // recur down lvalue; dispatch to check_if_path_is_moved when necessary
 529         let mut lvalue = lvalue;
 530         loop {
 531             match *lvalue {
 532                 Lvalue::Local(_) | Lvalue::Static(_) => {
 533                     // assigning to `x` does not require `x` be initialized.
 534                     break;
 535                 }
 536                 Lvalue::Projection(ref proj) => {
 537                     let Projection { ref base, ref elem } = **proj;
 538                     match *elem {
 539                         ProjectionElem::Deref |
 540                         // assigning to *P requires `P` initialized.
 541                         ProjectionElem::Index(_/*operand*/) |
 542                         ProjectionElem::ConstantIndex { .. } |
 543                         // assigning to P[i] requires `P` initialized.
 544                         ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
 545                         // assigning to (P->variant) is okay if assigning to `P` is okay
 546                         //
 547                         // FIXME: is this true even if P is a adt with a dtor?
 548                         { }
 549
 550                         ProjectionElem::Subslice { .. } => {
 551                             panic!("we dont allow assignments to subslices, context: {:?}",
 552                                    context);
 553                         }
 554
 555                         ProjectionElem::Field(..) => {
 556                             // if type of `P` has a dtor, then
 557                             // assigning to `P.f` requires `P` itself
 558                             // be already initialized
 559                             let tcx = self.tcx;
 560                             match base.ty(self.mir, tcx).to_ty(tcx).sty {
 561                                 ty::TyAdt(def, _) if def.has_dtor(tcx) => {
 562
 563                                     // FIXME: analogous code in
 564                                     // check_loans.rs first maps
 565                                     // `base` to its base_path.
 566
 567                                     self.check_if_path_is_moved(context,
 568                                                                 (base, span), flow_state);
 569
 570                                     // (base initialized; no need to
 571                                     // recur further)
 572                                     break;
 573                                 }
 574                                 _ => {}
 575                             }
 576                         }
 577                     }
 578
 579                     lvalue = base;
 580                     continue;
 581                 }
 582             }
 583         }
 584     }
 585
 586     fn check_for_conflicting_loans(&mut self,
 587                                    context: Context,
 588                                    _location: Location,
 589                                    _bk: BorrowKind,
 590                                    lvalue_span: (&Lvalue<'gcx>, Span),
 591                                    flow_state: &InProgress<'b, 'gcx>) {
 592         // NOTE FIXME: The analogous code in old borrowck
 593         // check_loans.rs is careful to iterate over every *issued*
 594         // loan, as opposed to just the in scope ones.
 595         //
 596         // (Or if you prefer, all the *other* iterations over loans
 597         // only consider loans that are in scope of some given
 598         // CodeExtent)
 599         //
 600         // The (currently skeletal) code here does not encode such a
 601         // distinction, which means it is almost certainly over
 602         // looking something.
 603         //
 604         // (It is probably going to reject code that should be
 605         // accepted, I suspect, by treated issued-but-out-of-scope
 606         // loans as issued-and-in-scope, and thus causing them to
 607         // interfere with other loans.)
 608         //
 609         // However, I just want to get something running, especially
 610         // since I am trying to move into new territory with NLL, so
 611         // lets get this going first, and then address the issued vs
 612         // in-scope distinction later.
 613
 614         let state = &flow_state.borrows;
 615         let data = &state.base_results.operator().borrows();
 616
 617         debug!("check_for_conflicting_loans location: {:?}", _location);
 618
 619         // does any loan generated here conflict with a previously issued loan?
 620         let mut loans_generated = 0;
 621         for (g, gen) in state.elems_generated().map(|g| (g, &data[g])) {
 622             loans_generated += 1;
 623             for (i, issued) in state.elems_incoming().map(|i| (i, &data[i])) {
 624                 debug!("check_for_conflicting_loans gen: {:?} issued: {:?} conflicts: {}",
 625                        (g, gen, self.base_path(&gen.lvalue),
 626                         self.restrictions(&gen.lvalue).collect::<Vec<_>>()),
 627                        (i, issued, self.base_path(&issued.lvalue),
 628                         self.restrictions(&issued.lvalue).collect::<Vec<_>>()),
 629                        self.conflicts_with(gen, issued));
 630                 if self.conflicts_with(gen, issued) {
 631                     self.report_conflicting_borrow(context, lvalue_span, gen, issued);
 632                 }
 633             }
 634         }
 635
 636         // MIR statically ensures each statement gens *at most one*
 637         // loan; mutual conflict (within a statement) can't arise.
 638         //
 639         // As safe-guard, assert that above property actually holds.
 640         assert!(loans_generated <= 1);
 641     } }
 642
 643 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 644     fn each_borrow_involving_path<F>(&mut self,
 645                                      _context: Context,
 646                                      lvalue: &Lvalue<'gcx>,
 647                                      flow_state: &InProgress<'b, 'gcx>,
 648                                      mut op: F)
 649         where F: FnMut(&mut Self, BorrowIndex, &BorrowData<'gcx>) -> Control
 650     {
 651         // FIXME: analogous code in check_loans first maps `lvalue` to
 652         // its base_path.
 653
 654         let domain = flow_state.borrows.base_results.operator();
 655         let data = domain.borrows();
 656
 657         // check for loan restricting path P being used. Accounts for
 658         // borrows of P, P.a.b, etc.
 659         for i in flow_state.borrows.elems_incoming() {
 660             // FIXME: check_loans.rs filtered this to "in scope"
 661             // loans; i.e. it took a scope S and checked that each
 662             // restriction's kill_scope was a superscope of S.
 663             let borrowed = &data[i];
 664             for restricted in self.restrictions(&borrowed.lvalue) {
 665                 if restricted == lvalue {
 666                     let ctrl = op(self, i, borrowed);
 667                     if ctrl == Control::Break { return; }
 668                 }
 669             }
 670         }
 671
 672         // check for loans (not restrictions) on any base path.
 673         // e.g. Rejects `{ let x = &mut a.b; let y = a.b.c; }`,
 674         // since that moves out of borrowed path `a.b`.
 675         //
 676         // Limiting to loans (not restrictions) keeps this one
 677         // working: `{ let x = &mut a.b; let y = a.c; }`
 678         let mut cursor = lvalue;
 679         loop {
 680             // FIXME: check_loans.rs invoked `op` *before* cursor
 681             // shift here.  Might just work (and even avoid redundant
 682             // errors?) given code above?  But for now, I want to try
 683             // doing what I think is more "natural" check.
 684             for i in flow_state.borrows.elems_incoming() {
 685                 let borrowed = &data[i];
 686                 if borrowed.lvalue == *cursor {
 687                     let ctrl = op(self, i, borrowed);
 688                     if ctrl == Control::Break { return; }
 689                 }
 690             }
 691
 692             match *cursor {
 693                 Lvalue::Local(_) | Lvalue::Static(_) => break,
 694                 Lvalue::Projection(ref proj) => cursor = &proj.base,
 695             }
 696         }
 697     }
 698 }
 699
 700 mod restrictions {
 701     use super::MirBorrowckCtxt;
 702
 703     use rustc::hir;
 704     use rustc::ty::{self, TyCtxt};
 705     use rustc::mir::{Lvalue, Mir, Operand, ProjectionElem};
 706
 707     pub(super) struct Restrictions<'c, 'tcx: 'c> {
 708         mir: &'c Mir<'tcx>,
 709         tcx: TyCtxt<'c, 'tcx, 'tcx>,
 710         lvalue_stack: Vec<&'c Lvalue<'tcx>>,
 711     }
 712
 713     impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 714         pub(super) fn restrictions<'d>(&self,
 715                                        lvalue: &'d Lvalue<'gcx>)
 716                                        -> Restrictions<'d, 'gcx> where 'b: 'd
 717         {
 718             let lvalue_stack = if self.has_restrictions(lvalue) { vec![lvalue] } else { vec![] };
 719             Restrictions { lvalue_stack: lvalue_stack, mir: self.mir, tcx: self.tcx }
 720         }
 721
 722         fn has_restrictions(&self, lvalue: &Lvalue<'gcx>) -> bool {
 723             let mut cursor = lvalue;
 724             loop {
 725                 let proj = match *cursor {
 726                     Lvalue::Local(_) => return true,
 727                     Lvalue::Static(_) => return false,
 728                     Lvalue::Projection(ref proj) => proj,
 729                 };
 730                 match proj.elem {
 731                     ProjectionElem::Index(..) |
 732                     ProjectionElem::ConstantIndex { .. } |
 733                     ProjectionElem::Downcast(..) |
 734                     ProjectionElem::Subslice { .. } |
 735                     ProjectionElem::Field(_/*field*/, _/*ty*/) => {
 736                         cursor = &proj.base;
 737                         continue;
 738                     }
 739                     ProjectionElem::Deref => {
 740                         let ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 741                         match ty.sty {
 742                             ty::TyRawPtr(_) => {
 743                                 return false;
 744                             }
 745                             ty::TyRef(_, ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
 746                                 // FIXME: do I need to check validity of
 747                                 // region here though? (I think the original
 748                                 // check_loans code did, like readme says)
 749                                 return false;
 750                             }
 751                             ty::TyRef(_, ty::TypeAndMut { ty: _, mutbl: hir::MutMutable }) => {
 752                                 cursor = &proj.base;
 753                                 continue;
 754                             }
 755                             ty::TyAdt(..) if ty.is_box() => {
 756                                 cursor = &proj.base;
 757                                 continue;
 758                             }
 759                             _ => {
 760                                 panic!("unknown type fed to Projection Deref.");
 761                             }
 762                         }
 763                     }
 764                 }
 765             }
 766         }
 767     }
 768
 769     impl<'c, 'tcx> Iterator for Restrictions<'c, 'tcx> {
 770         type Item = &'c Lvalue<'tcx>;
 771         fn next(&mut self) -> Option<Self::Item> {
 772             'pop: loop {
 773                 let lvalue = match self.lvalue_stack.pop() {
 774                     None => return None,
 775                     Some(lvalue) => lvalue,
 776                 };
 777
 778                 // `lvalue` may not be a restriction itself, but may
 779                 // hold one further down (e.g. we never return
 780                 // downcasts here, but may return a base of a
 781                 // downcast).
 782                 //
 783                 // Also, we need to enqueue any additional
 784                 // subrestrictions that it implies, since we can only
 785                 // return from from this call alone.
 786
 787                 let mut cursor = lvalue;
 788                 'cursor: loop {
 789                     let proj = match *cursor {
 790                         Lvalue::Local(_) => return Some(cursor), // search yielded this leaf
 791                         Lvalue::Static(_) => continue 'pop, // fruitless leaf; try next on stack
 792                         Lvalue::Projection(ref proj) => proj,
 793                     };
 794
 795                     match proj.elem {
 796                         ProjectionElem::Field(_/*field*/, _/*ty*/) => {
 797                             // FIXME: add union handling
 798                             self.lvalue_stack.push(&proj.base);
 799                             return Some(cursor);
 800                         }
 801                         ProjectionElem::Downcast(..) |
 802                         ProjectionElem::Subslice { .. } |
 803                         ProjectionElem::ConstantIndex { .. } |
 804                         ProjectionElem::Index(Operand::Constant(..)) => {
 805                             cursor = &proj.base;
 806                             continue 'cursor;
 807                         }
 808                         ProjectionElem::Index(Operand::Consume(ref index)) => {
 809                             self.lvalue_stack.push(index); // FIXME: did old borrowck do this?
 810                             cursor = &proj.base;
 811                             continue 'cursor;
 812                         }
 813                         ProjectionElem::Deref => {
 814                             // (handled below)
 815                         }
 816                     }
 817
 818                     assert_eq!(proj.elem, ProjectionElem::Deref);
 819
 820                     let ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 821                     match ty.sty {
 822                         ty::TyRawPtr(_) => {
 823                             // borrowck ignores raw ptrs; treat analogous to imm borrow
 824                             continue 'pop;
 825                         }
 826                         // R-Deref-Imm-Borrowed
 827                         ty::TyRef(_/*rgn*/, ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
 828                             // immutably-borrowed referents do not
 829                             // have recursively-implied restrictions
 830                             // (because preventing actions on `*LV`
 831                             // does nothing about aliases like `*LV1`)
 832
 833                             // FIXME: do I need to check validity of
 834                             // `_r` here though? (I think the original
 835                             // check_loans code did, like the readme
 836                             // says)
 837
 838                             // (And do I *really* not have to
 839                             // recursively process the `base` as a
 840                             // further search here? Leaving this `if
 841                             // false` here as a hint to look at this
 842                             // again later.
 843                             //
 844                             // Ah, it might be because the
 845                             // restrictions are distinct from the path
 846                             // substructure. Note that there is a
 847                             // separate loop over the path
 848                             // substructure in fn
 849                             // each_borrow_involving_path, for better
 850                             // or for worse.
 851
 852                             if false {
 853                                 cursor = &proj.base;
 854                                 continue 'cursor;
 855                             } else {
 856                                 continue 'pop;
 857                             }
 858                         }
 859
 860                         // R-Deref-Mut-Borrowed
 861                         ty::TyRef(_/*rgn*/, ty::TypeAndMut { ty: _, mutbl: hir::MutMutable }) => {
 862                             // mutably-borrowed referents are
 863                             // themselves restricted.
 864
 865                             // FIXME: do I need to check validity of
 866                             // `_r` here though? (I think the original
 867                             // check_loans code did, like the readme
 868                             // says)
 869
 870                             // schedule base for future iteration.
 871                             self.lvalue_stack.push(&proj.base);
 872                             return Some(cursor); // search yielded interior node
 873                         }
 874
 875                         // R-Deref-Send-Pointer
 876                         ty::TyAdt(..) if ty.is_box() => {
 877                             // borrowing interior of a box implies that
 878                             // its base can no longer be mutated (o/w box
 879                             // storage would be freed)
 880                             self.lvalue_stack.push(&proj.base);
 881                             return Some(cursor); // search yielded interior node
 882                         }
 883
 884                         _ => panic!("unknown type fed to Projection Deref."),
 885                     }
 886                 }
 887             }
 888         }
 889     }
 890 }
 891
 892 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 893     fn report_use_of_moved(&mut self,
 894                            _context: Context,
 895                            (lvalue, span): (&Lvalue, Span)) {
 896         let mut err = self.tcx.cannot_act_on_uninitialized_variable(
 897             span, "use", &self.describe_lvalue(lvalue), Origin::Mir);
 898         // FIXME: add span_label for use of uninitialized variable
 899         err.emit();
 900     }
 901
 902     fn report_move_out_while_borrowed(&mut self,
 903                                       _context: Context,
 904                                       (lvalue, span): (&Lvalue, Span)) {
 905         let mut err = self.tcx.cannot_move_when_borrowed(
 906             span, &self.describe_lvalue(lvalue), Origin::Mir);
 907         // FIXME 1: add span_label for "borrow of `()` occurs here"
 908         // FIXME 2: add span_label for "move out of `{}` occurs here"
 909         err.emit();
 910     }
 911
 912     fn report_use_while_mutably_borrowed(&mut self,
 913                                          _context: Context,
 914                                          (lvalue, span): (&Lvalue, Span)) {
 915         let mut err = self.tcx.cannot_use_when_mutably_borrowed(
 916             span, &self.describe_lvalue(lvalue), Origin::Mir);
 917         // FIXME 1: add span_label for "borrow of `()` occurs here"
 918         // FIXME 2: add span_label for "use of `{}` occurs here"
 919         err.emit();
 920     }
 921
 922     fn report_conflicting_borrow(&mut self,
 923                                  _context: Context,
 924                                  (lvalue, span): (&Lvalue, Span),
 925                                  loan1: &BorrowData,
 926                                  loan2: &BorrowData) {
 927         // FIXME: obviously falsifiable. Generalize for non-eq lvalues later.
 928         assert_eq!(loan1.lvalue, loan2.lvalue);
 929
 930         // FIXME: supply non-"" `opt_via` when appropriate
 931         let mut err = match (loan1.kind, "immutable", "mutable",
 932                              loan2.kind, "immutable", "mutable") {
 933             (BorrowKind::Shared, lft, _, BorrowKind::Mut, _, rgt) |
 934             (BorrowKind::Mut, _, lft, BorrowKind::Shared, rgt, _) |
 935             (BorrowKind::Mut, _, lft, BorrowKind::Mut, _, rgt) =>
 936                 self.tcx.cannot_reborrow_already_borrowed(
 937                     span, &self.describe_lvalue(lvalue),
 938                     "", lft, "it", rgt, "", Origin::Mir),
 939
 940             _ =>  self.tcx.cannot_mutably_borrow_multiply(
 941                 span, &self.describe_lvalue(lvalue), "", Origin::Mir),
 942             // FIXME: add span labels for first and second mutable borrows, as well as
 943             // end point for first.
 944         };
 945         err.emit();
 946     }
 947
 948     fn report_illegal_mutation_of_borrowed(&mut self, _: Context, (lvalue, span): (&Lvalue, Span)) {
 949         let mut err = self.tcx.cannot_assign_to_borrowed(
 950             span, &self.describe_lvalue(lvalue), Origin::Mir);
 951         // FIXME: add span labels for borrow and assignment points
 952         err.emit();
 953     }
 954
 955     fn report_illegal_reassignment(&mut self, _context: Context, (lvalue, span): (&Lvalue, Span)) {
 956         let mut err = self.tcx.cannot_reassign_immutable(
 957             span, &self.describe_lvalue(lvalue), Origin::Mir);
 958         // FIXME: add span labels for borrow and assignment points
 959         err.emit();
 960     }
 961
 962     fn report_assignment_to_static(&mut self, _context: Context, (lvalue, span): (&Lvalue, Span)) {
 963         let mut err = self.tcx.cannot_assign_static(
 964             span, &self.describe_lvalue(lvalue), Origin::Mir);
 965         // FIXME: add span labels for borrow and assignment points
 966         err.emit();
 967     }
 968 }
 969
 970 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 971     // End-user visible description of `lvalue`
 972     fn describe_lvalue(&self, lvalue: &Lvalue) -> String {
 973         let mut buf = String::new();
 974         self.append_lvalue_to_string(lvalue, &mut buf);
 975         buf
 976     }
 977
 978     // Appends end-user visible description of `lvalue` to `buf`.
 979     fn append_lvalue_to_string(&self, lvalue: &Lvalue, buf: &mut String) {
 980         match *lvalue {
 981             Lvalue::Local(local) => {
 982                 let local = &self.mir.local_decls[local];
 983                 match local.name {
 984                     Some(name) => buf.push_str(&format!("{}", name)),
 985                     None => buf.push_str("_"),
 986                 }
 987             }
 988             Lvalue::Static(ref static_) => {
 989                 buf.push_str(&format!("{}", &self.tcx.item_name(static_.def_id)));
 990             }
 991             Lvalue::Projection(ref proj) => {
 992                 let (prefix, suffix, index_operand) = match proj.elem {
 993                     ProjectionElem::Deref =>
 994                         ("(*", format!(")"), None),
 995                     ProjectionElem::Downcast(..) =>
 996                         ("",   format!(""), None), // (dont emit downcast info)
 997                     ProjectionElem::Field(field, _ty) =>
 998                         ("",   format!(".{}", field.index()), None),
 999                     ProjectionElem::Index(ref index) =>
1000                         ("",   format!(""), Some(index)),
1001                     ProjectionElem::ConstantIndex { offset, min_length, from_end: true } =>
1002                         ("",   format!("[{} of {}]", offset, min_length), None),
1003                     ProjectionElem::ConstantIndex { offset, min_length, from_end: false } =>
1004                         ("",   format!("[-{} of {}]", offset, min_length), None),
1005                     ProjectionElem::Subslice { from, to: 0 } =>
1006                         ("",   format!("[{}:]", from), None),
1007                     ProjectionElem::Subslice { from: 0, to } =>
1008                         ("",   format!("[:-{}]", to), None),
1009                     ProjectionElem::Subslice { from, to } =>
1010                         ("",   format!("[{}:-{}]", from, to), None),
1011                 };
1012                 buf.push_str(prefix);
1013                 self.append_lvalue_to_string(&proj.base, buf);
1014                 if let Some(index) = index_operand {
1015                     buf.push_str("[");
1016                     self.append_operand_to_string(index, buf);
1017                     buf.push_str("]");
1018                 } else {
1019                     buf.push_str(&suffix);
1020                 }
1021
1022             }
1023         }
1024     }
1025
1026     fn append_operand_to_string(&self, operand: &Operand, buf: &mut String) {
1027         match *operand {
1028             Operand::Consume(ref lvalue) => {
1029                 self.append_lvalue_to_string(lvalue, buf);
1030             }
1031             Operand::Constant(ref constant) => {
1032                 buf.push_str(&format!("{:?}", constant));
1033             }
1034         }
1035     }
1036 }
1037
1038 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
1039     // FIXME: needs to be able to express errors analogous to check_loans.rs
1040     fn conflicts_with(&self, loan1: &BorrowData<'gcx>, loan2: &BorrowData<'gcx>) -> bool {
1041         if loan1.compatible_with(loan2.kind) { return false; }
1042
1043         let loan2_base_path = self.base_path(&loan2.lvalue);
1044         for restricted in self.restrictions(&loan1.lvalue) {
1045             if restricted != loan2_base_path { continue; }
1046             return true;
1047         }
1048
1049         let loan1_base_path = self.base_path(&loan1.lvalue);
1050         for restricted in self.restrictions(&loan2.lvalue) {
1051             if restricted != loan1_base_path { continue; }
1052             return true;
1053         }
1054
1055         return false;
1056     }
1057
1058     // FIXME (#16118): function intended to allow the borrow checker
1059     // to be less precise in its handling of Box while still allowing
1060     // moves out of a Box. They should be removed when/if we stop
1061     // treating Box specially (e.g. when/if DerefMove is added...)
1062
1063     fn base_path<'d>(&self, lvalue: &'d Lvalue<'gcx>) -> &'d Lvalue<'gcx> {
1064         //! Returns the base of the leftmost (deepest) dereference of an
1065         //! Box in `lvalue`. If there is no dereference of an Box
1066         //! in `lvalue`, then it just returns `lvalue` itself.
1067
1068         let mut cursor = lvalue;
1069         let mut deepest = lvalue;
1070         loop {
1071             let proj = match *cursor {
1072                 Lvalue::Local(..) | Lvalue::Static(..) => return deepest,
1073                 Lvalue::Projection(ref proj) => proj,
1074             };
1075             if proj.elem == ProjectionElem::Deref &&
1076                 lvalue.ty(self.mir, self.tcx).to_ty(self.tcx).is_box()
1077             {
1078                 deepest = &proj.base;
1079             }
1080             cursor = &proj.base;
1081         }
1082     }
1083 }
1084
1085 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1086 struct Context {
1087     kind: ContextKind,
1088     loc: Location,
1089 }
1090
1091 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1092 enum ContextKind {
1093     AssignLhs,
1094     AssignRhs,
1095     SetDiscrim,
1096     InlineAsm,
1097     SwitchInt,
1098     Drop,
1099     DropAndReplace,
1100     CallOperator,
1101     CallOperand,
1102     CallDest,
1103     Assert,
1104     StorageDead,
1105 }
1106
1107 impl ContextKind {
1108     fn new(self, loc: Location) -> Context { Context { kind: self, loc: loc } }
1109 }
1110
1111 impl<'b, 'tcx: 'b> InProgress<'b, 'tcx> {
1112     pub(super) fn new(borrows: DataflowResults<Borrows<'b, 'tcx>>,
1113                       inits: DataflowResults<MaybeInitializedLvals<'b, 'tcx>>,
1114                       uninits: DataflowResults<MaybeUninitializedLvals<'b, 'tcx>>)
1115                       -> Self {
1116         InProgress {
1117             borrows: FlowInProgress::new(borrows),
1118             inits: FlowInProgress::new(inits),
1119             uninits: FlowInProgress::new(uninits),
1120         }
1121     }
1122
1123     fn each_flow<XB, XI, XU>(&mut self,
1124                              mut xform_borrows: XB,
1125                              mut xform_inits: XI,
1126                              mut xform_uninits: XU) where
1127         XB: FnMut(&mut FlowInProgress<Borrows<'b, 'tcx>>),
1128         XI: FnMut(&mut FlowInProgress<MaybeInitializedLvals<'b, 'tcx>>),
1129         XU: FnMut(&mut FlowInProgress<MaybeUninitializedLvals<'b, 'tcx>>),
1130     {
1131         xform_borrows(&mut self.borrows);
1132         xform_inits(&mut self.inits);
1133         xform_uninits(&mut self.uninits);
1134     }
1135
1136     fn summary(&self) -> String {
1137         let mut s = String::new();
1138
1139         s.push_str("borrows in effect: [");
1140         let mut saw_one = false;
1141         self.borrows.each_state_bit(|borrow| {
1142             if saw_one { s.push_str(", "); };
1143             saw_one = true;
1144             let borrow_data = &self.borrows.base_results.operator().borrows()[borrow];
1145             s.push_str(&format!("{}", borrow_data));
1146         });
1147         s.push_str("] ");
1148
1149         s.push_str("borrows generated: [");
1150         let mut saw_one = false;
1151         self.borrows.each_gen_bit(|borrow| {
1152             if saw_one { s.push_str(", "); };
1153             saw_one = true;
1154             let borrow_data = &self.borrows.base_results.operator().borrows()[borrow];
1155             s.push_str(&format!("{}", borrow_data));
1156         });
1157         s.push_str("] ");
1158
1159         s.push_str("inits: [");
1160         let mut saw_one = false;
1161         self.inits.each_state_bit(|mpi_init| {
1162             if saw_one { s.push_str(", "); };
1163             saw_one = true;
1164             let move_path =
1165                 &self.inits.base_results.operator().move_data().move_paths[mpi_init];
1166             s.push_str(&format!("{}", move_path));
1167         });
1168         s.push_str("] ");
1169
1170         s.push_str("uninits: [");
1171         let mut saw_one = false;
1172         self.uninits.each_state_bit(|mpi_uninit| {
1173             if saw_one { s.push_str(", "); };
1174             saw_one = true;
1175             let move_path =
1176                 &self.uninits.base_results.operator().move_data().move_paths[mpi_uninit];
1177             s.push_str(&format!("{}", move_path));
1178         });
1179         s.push_str("]");
1180
1181         return s;
1182     }
1183 }
1184
1185 impl<BD> FlowInProgress<BD> where BD: BitDenotation {
1186     fn each_state_bit<F>(&self, f: F) where F: FnMut(BD::Idx) {
1187         self.curr_state.each_bit(self.base_results.operator().bits_per_block(), f)
1188     }
1189
1190     fn each_gen_bit<F>(&self, f: F) where F: FnMut(BD::Idx) {
1191         self.stmt_gen.each_bit(self.base_results.operator().bits_per_block(), f)
1192     }
1193
1194     fn new(results: DataflowResults<BD>) -> Self {
1195         let bits_per_block = results.sets().bits_per_block();
1196         let curr_state = IdxSetBuf::new_empty(bits_per_block);
1197         let stmt_gen = IdxSetBuf::new_empty(bits_per_block);
1198         let stmt_kill = IdxSetBuf::new_empty(bits_per_block);
1199         FlowInProgress {
1200             base_results: results,
1201             curr_state: curr_state,
1202             stmt_gen: stmt_gen,
1203             stmt_kill: stmt_kill,
1204         }
1205     }
1206
1207     fn reset_to_entry_of(&mut self, bb: BasicBlock) {
1208         (*self.curr_state).clone_from(self.base_results.sets().on_entry_set_for(bb.index()));
1209     }
1210
1211     fn reconstruct_statement_effect(&mut self, loc: Location) {
1212         self.stmt_gen.reset_to_empty();
1213         self.stmt_kill.reset_to_empty();
1214         let mut ignored = IdxSetBuf::new_empty(0);
1215         let mut sets = BlockSets {
1216             on_entry: &mut ignored, gen_set: &mut self.stmt_gen, kill_set: &mut self.stmt_kill,
1217         };
1218         self.base_results.operator().statement_effect(&mut sets, loc);
1219     }
1220
1221     fn reconstruct_terminator_effect(&mut self, loc: Location) {
1222         self.stmt_gen.reset_to_empty();
1223         self.stmt_kill.reset_to_empty();
1224         let mut ignored = IdxSetBuf::new_empty(0);
1225         let mut sets = BlockSets {
1226             on_entry: &mut ignored, gen_set: &mut self.stmt_gen, kill_set: &mut self.stmt_kill,
1227         };
1228         self.base_results.operator().terminator_effect(&mut sets, loc);
1229     }
1230
1231     fn apply_local_effect(&mut self) {
1232         self.curr_state.union(&self.stmt_gen);
1233         self.curr_state.subtract(&self.stmt_kill);
1234     }
1235
1236     fn elems_generated(&self) -> indexed_set::Elems<BD::Idx> {
1237         let univ = self.base_results.sets().bits_per_block();
1238         self.stmt_gen.elems(univ)
1239     }
1240
1241     fn elems_incoming(&self) -> indexed_set::Elems<BD::Idx> {
1242         let univ = self.base_results.sets().bits_per_block();
1243         self.curr_state.elems(univ)
1244     }
1245 }
1246
1247 impl<'tcx> BorrowData<'tcx> {
1248     fn compatible_with(&self, bk: BorrowKind) -> bool {
1249         match (self.kind, bk) {
1250             (BorrowKind::Shared, BorrowKind::Shared) => true,
1251
1252             (BorrowKind::Mut, _) |
1253             (BorrowKind::Unique, _) |
1254             (_, BorrowKind::Mut) |
1255             (_, BorrowKind::Unique) => false,
1256         }
1257     }
1258 }