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