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;
  14 use rustc::hir::def_id::{DefId};
  15 use rustc::infer::{InferCtxt};
  16 use rustc::ty::{self, TyCtxt, ParamEnv};
  17 use rustc::ty::maps::Providers;
  18 use rustc::mir::{AssertMessage, BasicBlock, BorrowKind, Location, Lvalue, Local};
  19 use rustc::mir::{Mir, Mutability, Operand, Projection, ProjectionElem, Rvalue};
  20 use rustc::mir::{Statement, StatementKind, Terminator, TerminatorKind};
  21 use transform::nll;
  22
  23 use rustc_data_structures::indexed_set::{self, IdxSetBuf};
  24 use rustc_data_structures::indexed_vec::{Idx};
  25
  26 use syntax::ast::{self};
  27 use syntax_pos::{DUMMY_SP, Span};
  28
  29 use dataflow::{do_dataflow};
  30 use dataflow::{MoveDataParamEnv};
  31 use dataflow::{BitDenotation, BlockSets, DataflowResults, DataflowResultsConsumer};
  32 use dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
  33 use dataflow::{MovingOutStatements};
  34 use dataflow::{Borrows, BorrowData, BorrowIndex};
  35 use dataflow::move_paths::{MoveError, IllegalMoveOriginKind};
  36 use dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex, LookupResult, MoveOutIndex};
  37 use util::borrowck_errors::{BorrowckErrors, Origin};
  38
  39 use self::MutateMode::{JustWrite, WriteAndRead};
  40 use self::ConsumeKind::{Consume};
  41
  42
  43 pub fn provide(providers: &mut Providers) {
  44     *providers = Providers {
  45         mir_borrowck,
  46         ..*providers
  47     };
  48 }
  49
  50 fn mir_borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) {
  51     let input_mir = tcx.mir_validated(def_id);
  52     debug!("run query mir_borrowck: {}", tcx.item_path_str(def_id));
  53
  54     if {
  55         !tcx.has_attr(def_id, "rustc_mir_borrowck") &&
  56             !tcx.sess.opts.debugging_opts.borrowck_mir &&
  57             !tcx.sess.opts.debugging_opts.nll
  58     } {
  59         return;
  60     }
  61
  62     tcx.infer_ctxt().enter(|infcx| {
  63         let input_mir: &Mir = &input_mir.borrow();
  64         do_mir_borrowck(&infcx, input_mir, def_id);
  65     });
  66     debug!("mir_borrowck done");
  67 }
  68
  69 fn do_mir_borrowck<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
  70                                    input_mir: &Mir<'gcx>,
  71                                    def_id: DefId)
  72 {
  73     let tcx = infcx.tcx;
  74     let attributes = tcx.get_attrs(def_id);
  75     let param_env = tcx.param_env(def_id);
  76     let id = tcx.hir.as_local_node_id(def_id)
  77         .expect("do_mir_borrowck: non-local DefId");
  78
  79     let move_data: MoveData<'tcx> = match MoveData::gather_moves(input_mir, tcx, param_env) {
  80         Ok(move_data) => move_data,
  81         Err((move_data, move_errors)) => {
  82             for move_error in move_errors {
  83                 let (span, kind): (Span, IllegalMoveOriginKind) = match move_error {
  84                     MoveError::UnionMove { .. } =>
  85                         unimplemented!("dont know how to report union move errors yet."),
  86                     MoveError::IllegalMove { cannot_move_out_of: o } => (o.span, o.kind),
  87                 };
  88                 let origin = Origin::Mir;
  89                 let mut err = match kind {
  90                     IllegalMoveOriginKind::Static =>
  91                         tcx.cannot_move_out_of(span, "static item", origin),
  92                     IllegalMoveOriginKind::BorrowedContent =>
  93                         tcx.cannot_move_out_of(span, "borrowed_content", origin),
  94                     IllegalMoveOriginKind::InteriorOfTypeWithDestructor { container_ty: ty } =>
  95                         tcx.cannot_move_out_of_interior_of_drop(span, ty, origin),
  96                     IllegalMoveOriginKind::InteriorOfSlice { elem_ty: ty, is_index } =>
  97                         tcx.cannot_move_out_of_interior_noncopy(span, ty, is_index, origin),
  98                     IllegalMoveOriginKind::InteriorOfArray { elem_ty: ty, is_index } =>
  99                         tcx.cannot_move_out_of_interior_noncopy(span, ty, is_index, origin),
 100                 };
 101                 err.emit();
 102             }
 103             move_data
 104         }
 105     };
 106
 107     // Make our own copy of the MIR. This copy will be modified (in place) to
 108     // contain non-lexical lifetimes. It will have a lifetime tied
 109     // to the inference context.
 110     let mut mir: Mir<'tcx> = input_mir.clone();
 111     let mir = &mut mir;
 112
 113     // If we are in non-lexical mode, compute the non-lexical lifetimes.
 114     let opt_regioncx = if !tcx.sess.opts.debugging_opts.nll {
 115         None
 116     } else {
 117         Some(nll::compute_regions(infcx, def_id, mir))
 118     };
 119
 120     let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env };
 121     let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
 122     let flow_borrows = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
 123                                    Borrows::new(tcx, mir, opt_regioncx.as_ref()),
 124                                    |bd, i| bd.location(i));
 125     let flow_inits = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
 126                                  MaybeInitializedLvals::new(tcx, mir, &mdpe),
 127                                  |bd, i| &bd.move_data().move_paths[i]);
 128     let flow_uninits = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
 129                                    MaybeUninitializedLvals::new(tcx, mir, &mdpe),
 130                                    |bd, i| &bd.move_data().move_paths[i]);
 131     let flow_move_outs = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
 132                                      MovingOutStatements::new(tcx, mir, &mdpe),
 133                                      |bd, i| &bd.move_data().moves[i]);
 134
 135     let mut mbcx = MirBorrowckCtxt {
 136         tcx: tcx,
 137         mir: mir,
 138         node_id: id,
 139         move_data: &mdpe.move_data,
 140         param_env: param_env,
 141         fake_infer_ctxt: &infcx,
 142     };
 143
 144     let mut state = InProgress::new(flow_borrows,
 145                                     flow_inits,
 146                                     flow_uninits,
 147                                     flow_move_outs);
 148
 149     mbcx.analyze_results(&mut state); // entry point for DataflowResultsConsumer
 150 }
 151
 152 #[allow(dead_code)]
 153 pub struct MirBorrowckCtxt<'c, 'b, 'a: 'b+'c, 'gcx: 'a+'tcx, 'tcx: 'a> {
 154     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 155     mir: &'b Mir<'tcx>,
 156     node_id: ast::NodeId,
 157     move_data: &'b MoveData<'tcx>,
 158     param_env: ParamEnv<'tcx>,
 159     fake_infer_ctxt: &'c InferCtxt<'c, 'gcx, 'tcx>,
 160 }
 161
 162 // (forced to be `pub` due to its use as an associated type below.)
 163 pub struct InProgress<'b, 'gcx: 'tcx, 'tcx: 'b> {
 164     borrows: FlowInProgress<Borrows<'b, 'gcx, 'tcx>>,
 165     inits: FlowInProgress<MaybeInitializedLvals<'b, 'gcx, 'tcx>>,
 166     uninits: FlowInProgress<MaybeUninitializedLvals<'b, 'gcx, 'tcx>>,
 167     move_outs: FlowInProgress<MovingOutStatements<'b, 'gcx, 'tcx>>,
 168 }
 169
 170 struct FlowInProgress<BD> where BD: BitDenotation {
 171     base_results: DataflowResults<BD>,
 172     curr_state: IdxSetBuf<BD::Idx>,
 173     stmt_gen: IdxSetBuf<BD::Idx>,
 174     stmt_kill: IdxSetBuf<BD::Idx>,
 175 }
 176
 177 // Check that:
 178 // 1. assignments are always made to mutable locations (FIXME: does that still really go here?)
 179 // 2. loans made in overlapping scopes do not conflict
 180 // 3. assignments do not affect things loaned out as immutable
 181 // 4. moves do not affect things loaned out in any way
 182 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> DataflowResultsConsumer<'b, 'tcx>
 183     for MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
 184 {
 185     type FlowState = InProgress<'b, 'gcx, 'tcx>;
 186
 187     fn mir(&self) -> &'b Mir<'tcx> { self.mir }
 188
 189     fn reset_to_entry_of(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
 190         flow_state.each_flow(|b| b.reset_to_entry_of(bb),
 191                              |i| i.reset_to_entry_of(bb),
 192                              |u| u.reset_to_entry_of(bb),
 193                              |m| m.reset_to_entry_of(bb));
 194     }
 195
 196     fn reconstruct_statement_effect(&mut self,
 197                                     location: Location,
 198                                     flow_state: &mut Self::FlowState) {
 199         flow_state.each_flow(|b| b.reconstruct_statement_effect(location),
 200                              |i| i.reconstruct_statement_effect(location),
 201                              |u| u.reconstruct_statement_effect(location),
 202                              |m| m.reconstruct_statement_effect(location));
 203     }
 204
 205     fn apply_local_effect(&mut self,
 206                           _location: Location,
 207                           flow_state: &mut Self::FlowState) {
 208         flow_state.each_flow(|b| b.apply_local_effect(),
 209                              |i| i.apply_local_effect(),
 210                              |u| u.apply_local_effect(),
 211                              |m| m.apply_local_effect());
 212     }
 213
 214     fn reconstruct_terminator_effect(&mut self,
 215                                      location: Location,
 216                                      flow_state: &mut Self::FlowState) {
 217         flow_state.each_flow(|b| b.reconstruct_terminator_effect(location),
 218                              |i| i.reconstruct_terminator_effect(location),
 219                              |u| u.reconstruct_terminator_effect(location),
 220                              |m| m.reconstruct_terminator_effect(location));
 221     }
 222
 223     fn visit_block_entry(&mut self,
 224                          bb: BasicBlock,
 225                          flow_state: &Self::FlowState) {
 226         let summary = flow_state.summary();
 227         debug!("MirBorrowckCtxt::process_block({:?}): {}", bb, summary);
 228     }
 229
 230     fn visit_statement_entry(&mut self,
 231                              location: Location,
 232                              stmt: &Statement<'tcx>,
 233                              flow_state: &Self::FlowState) {
 234         let summary = flow_state.summary();
 235         debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {}", location, stmt, summary);
 236         let span = stmt.source_info.span;
 237         match stmt.kind {
 238             StatementKind::Assign(ref lhs, ref rhs) => {
 239                 // NOTE: NLL RFC calls for *shallow* write; using Deep
 240                 // for short-term compat w/ AST-borrowck. Also, switch
 241                 // to shallow requires to dataflow: "if this is an
 242                 // assignment `lv = <rvalue>`, then any loan for some
 243                 // path P of which `lv` is a prefix is killed."
 244                 self.mutate_lvalue(ContextKind::AssignLhs.new(location),
 245                                    (lhs, span), Deep, JustWrite, flow_state);
 246
 247                 self.consume_rvalue(ContextKind::AssignRhs.new(location),
 248                                     (rhs, span), location, flow_state);
 249             }
 250             StatementKind::SetDiscriminant { ref lvalue, variant_index: _ } => {
 251                 self.mutate_lvalue(ContextKind::SetDiscrim.new(location),
 252                                    (lvalue, span),
 253                                    Shallow(Some(ArtificialField::Discriminant)),
 254                                    JustWrite,
 255                                    flow_state);
 256             }
 257             StatementKind::InlineAsm { ref asm, ref outputs, ref inputs } => {
 258                 for (o, output) in asm.outputs.iter().zip(outputs) {
 259                     if o.is_indirect {
 260                         self.consume_lvalue(ContextKind::InlineAsm.new(location),
 261                                             Consume,
 262                                             (output, span),
 263                                             flow_state);
 264                     } else {
 265                         self.mutate_lvalue(ContextKind::InlineAsm.new(location),
 266                                            (output, span),
 267                                            Deep,
 268                                            if o.is_rw { WriteAndRead } else { JustWrite },
 269                                            flow_state);
 270                     }
 271                 }
 272                 for input in inputs {
 273                     self.consume_operand(ContextKind::InlineAsm.new(location),
 274                                          Consume,
 275                                          (input, span), flow_state);
 276                 }
 277             }
 278             StatementKind::EndRegion(ref _rgn) => {
 279                 // ignored when consuming results (update to
 280                 // flow_state already handled).
 281             }
 282             StatementKind::Nop |
 283             StatementKind::Validate(..) |
 284             StatementKind::StorageLive(..) => {
 285                 // `Nop`, `Validate`, and `StorageLive` are irrelevant
 286                 // to borrow check.
 287             }
 288
 289             StatementKind::StorageDead(local) => {
 290                 self.access_lvalue(ContextKind::StorageDead.new(location),
 291                                    (&Lvalue::Local(local), span),
 292                                    (Shallow(None), Write(WriteKind::StorageDead)),
 293                                    flow_state);
 294             }
 295         }
 296     }
 297
 298     fn visit_terminator_entry(&mut self,
 299                               location: Location,
 300                               term: &Terminator<'tcx>,
 301                               flow_state: &Self::FlowState) {
 302         let loc = location;
 303         let summary = flow_state.summary();
 304         debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {}", location, term, summary);
 305         let span = term.source_info.span;
 306         match term.kind {
 307             TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => {
 308                 self.consume_operand(ContextKind::SwitchInt.new(loc),
 309                                      Consume,
 310                                      (discr, span), flow_state);
 311             }
 312             TerminatorKind::Drop { location: ref drop_lvalue, target: _, unwind: _ } => {
 313                 self.consume_lvalue(ContextKind::Drop.new(loc),
 314                                     ConsumeKind::Drop,
 315                                     (drop_lvalue, span), flow_state);
 316             }
 317             TerminatorKind::DropAndReplace { location: ref drop_lvalue,
 318                                              value: ref new_value,
 319                                              target: _,
 320                                              unwind: _ } => {
 321                 self.mutate_lvalue(ContextKind::DropAndReplace.new(loc),
 322                                    (drop_lvalue, span),
 323                                    Deep,
 324                                    JustWrite,
 325                                    flow_state);
 326                 self.consume_operand(ContextKind::DropAndReplace.new(loc),
 327                                      ConsumeKind::Drop,
 328                                      (new_value, span), flow_state);
 329             }
 330             TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => {
 331                 self.consume_operand(ContextKind::CallOperator.new(loc),
 332                                      Consume,
 333                                      (func, span), flow_state);
 334                 for arg in args {
 335                     self.consume_operand(ContextKind::CallOperand.new(loc),
 336                                          Consume,
 337                                          (arg, span), flow_state);
 338                 }
 339                 if let Some((ref dest, _/*bb*/)) = *destination {
 340                     self.mutate_lvalue(ContextKind::CallDest.new(loc),
 341                                        (dest, span),
 342                                        Deep,
 343                                        JustWrite,
 344                                        flow_state);
 345                 }
 346             }
 347             TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
 348                 self.consume_operand(ContextKind::Assert.new(loc),
 349                                      Consume,
 350                                      (cond, span), flow_state);
 351                 match *msg {
 352                     AssertMessage::BoundsCheck { ref len, ref index } => {
 353                         self.consume_operand(ContextKind::Assert.new(loc),
 354                                              Consume,
 355                                              (len, span), flow_state);
 356                         self.consume_operand(ContextKind::Assert.new(loc),
 357                                              Consume,
 358                                              (index, span), flow_state);
 359                     }
 360                     AssertMessage::Math(_/*const_math_err*/) => {}
 361                     AssertMessage::GeneratorResumedAfterReturn => {}
 362                     AssertMessage::GeneratorResumedAfterPanic => {}
 363                 }
 364             }
 365
 366             TerminatorKind::Yield { ref value, resume: _, drop: _} => {
 367                 self.consume_operand(ContextKind::Yield.new(loc),
 368                                      Consume, (value, span), flow_state);
 369             }
 370
 371             TerminatorKind::Goto { target: _ } |
 372             TerminatorKind::Resume |
 373             TerminatorKind::Return |
 374             TerminatorKind::GeneratorDrop |
 375             TerminatorKind::Unreachable |
 376             TerminatorKind::FalseEdges { .. } => {
 377                 // no data used, thus irrelevant to borrowck
 378             }
 379         }
 380     }
 381 }
 382
 383 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 384 enum MutateMode { JustWrite, WriteAndRead }
 385
 386 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 387 enum ConsumeKind { Drop, Consume }
 388
 389 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 390 enum Control { Continue, Break }
 391
 392 use self::ShallowOrDeep::{Shallow, Deep};
 393 use self::ReadOrWrite::{Read, Write};
 394
 395 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 396 enum ArtificialField {
 397     Discriminant,
 398     ArrayLength,
 399 }
 400
 401 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 402 enum ShallowOrDeep {
 403     /// From the RFC: "A *shallow* access means that the immediate
 404     /// fields reached at LV are accessed, but references or pointers
 405     /// found within are not dereferenced. Right now, the only access
 406     /// that is shallow is an assignment like `x = ...;`, which would
 407     /// be a *shallow write* of `x`."
 408     Shallow(Option<ArtificialField>),
 409
 410     /// From the RFC: "A *deep* access means that all data reachable
 411     /// through the given lvalue may be invalidated or accesses by
 412     /// this action."
 413     Deep,
 414 }
 415
 416 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 417 enum ReadOrWrite {
 418     /// From the RFC: "A *read* means that the existing data may be
 419     /// read, but will not be changed."
 420     Read(ReadKind),
 421
 422     /// From the RFC: "A *write* means that the data may be mutated to
 423     /// new values or otherwise invalidated (for example, it could be
 424     /// de-initialized, as in a move operation).
 425     Write(WriteKind),
 426 }
 427
 428 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 429 enum ReadKind {
 430     Borrow(BorrowKind),
 431     Copy,
 432 }
 433
 434 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 435 enum WriteKind {
 436     StorageDead,
 437     MutableBorrow(BorrowKind),
 438     Mutate,
 439     Move,
 440 }
 441
 442 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 443     fn access_lvalue(&mut self,
 444                      context: Context,
 445                      lvalue_span: (&Lvalue<'tcx>, Span),
 446                      kind: (ShallowOrDeep, ReadOrWrite),
 447                      flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 448
 449         let (sd, rw) = kind;
 450
 451         // Check permissions
 452         self.check_access_permissions(lvalue_span, rw);
 453
 454         self.each_borrow_involving_path(
 455             context, (sd, lvalue_span.0), flow_state, |this, _index, borrow, common_prefix| {
 456                 match (rw, borrow.kind) {
 457                     (Read(_), BorrowKind::Shared) => {
 458                         Control::Continue
 459                     }
 460                     (Read(kind), BorrowKind::Unique) |
 461                     (Read(kind), BorrowKind::Mut) => {
 462                         match kind {
 463                             ReadKind::Copy =>
 464                                 this.report_use_while_mutably_borrowed(
 465                                     context, lvalue_span, borrow),
 466                             ReadKind::Borrow(bk) => {
 467                                 let end_issued_loan_span =
 468                                     flow_state.borrows.base_results.operator().opt_region_end_span(
 469                                         &borrow.region);
 470                                 this.report_conflicting_borrow(
 471                                     context, common_prefix, lvalue_span, bk,
 472                                     &borrow, end_issued_loan_span)
 473                             }
 474                         }
 475                         Control::Break
 476                     }
 477                     (Write(kind), _) => {
 478                         match kind {
 479                             WriteKind::MutableBorrow(bk) => {
 480                                 let end_issued_loan_span =
 481                                     flow_state.borrows.base_results.operator().opt_region_end_span(
 482                                         &borrow.region);
 483                                 this.report_conflicting_borrow(
 484                                     context, common_prefix, lvalue_span, bk,
 485                                     &borrow, end_issued_loan_span)
 486                             }
 487                             WriteKind::StorageDead |
 488                             WriteKind::Mutate =>
 489                                 this.report_illegal_mutation_of_borrowed(
 490                                     context, lvalue_span, borrow),
 491                             WriteKind::Move =>
 492                                 this.report_move_out_while_borrowed(
 493                                     context, lvalue_span, &borrow),
 494                         }
 495                         Control::Break
 496                     }
 497                 }
 498             });
 499     }
 500
 501     fn mutate_lvalue(&mut self,
 502                      context: Context,
 503                      lvalue_span: (&Lvalue<'tcx>, Span),
 504                      kind: ShallowOrDeep,
 505                      mode: MutateMode,
 506                      flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 507         // Write of P[i] or *P, or WriteAndRead of any P, requires P init'd.
 508         match mode {
 509             MutateMode::WriteAndRead => {
 510                 self.check_if_path_is_moved(context, "update", lvalue_span, flow_state);
 511             }
 512             MutateMode::JustWrite => {
 513                 self.check_if_assigned_path_is_moved(context, lvalue_span, flow_state);
 514             }
 515         }
 516
 517         self.access_lvalue(context, lvalue_span, (kind, Write(WriteKind::Mutate)), flow_state);
 518
 519         // check for reassignments to immutable local variables
 520         self.check_if_reassignment_to_immutable_state(context, lvalue_span, flow_state);
 521     }
 522
 523     fn consume_rvalue(&mut self,
 524                       context: Context,
 525                       (rvalue, span): (&Rvalue<'tcx>, Span),
 526                       _location: Location,
 527                       flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 528         match *rvalue {
 529             Rvalue::Ref(_/*rgn*/, bk, ref lvalue) => {
 530                 let access_kind = match bk {
 531                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
 532                     BorrowKind::Unique |
 533                     BorrowKind::Mut => (Deep, Write(WriteKind::MutableBorrow(bk))),
 534                 };
 535                 self.access_lvalue(context, (lvalue, span), access_kind, flow_state);
 536                 self.check_if_path_is_moved(context, "borrow", (lvalue, span), flow_state);
 537             }
 538
 539             Rvalue::Use(ref operand) |
 540             Rvalue::Repeat(ref operand, _) |
 541             Rvalue::UnaryOp(_/*un_op*/, ref operand) |
 542             Rvalue::Cast(_/*cast_kind*/, ref operand, _/*ty*/) => {
 543                 self.consume_operand(context, Consume, (operand, span), flow_state)
 544             }
 545
 546             Rvalue::Len(ref lvalue) |
 547             Rvalue::Discriminant(ref lvalue) => {
 548                 let af = match *rvalue {
 549                     Rvalue::Len(..) => ArtificialField::ArrayLength,
 550                     Rvalue::Discriminant(..) => ArtificialField::Discriminant,
 551                     _ => unreachable!(),
 552                 };
 553                 self.access_lvalue(
 554                     context, (lvalue, span), (Shallow(Some(af)), Read(ReadKind::Copy)), flow_state);
 555                 self.check_if_path_is_moved(context, "use", (lvalue, span), flow_state);
 556             }
 557
 558             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2) |
 559             Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
 560                 self.consume_operand(context, Consume, (operand1, span), flow_state);
 561                 self.consume_operand(context, Consume, (operand2, span), flow_state);
 562             }
 563
 564             Rvalue::NullaryOp(_op, _ty) => {
 565                 // nullary ops take no dynamic input; no borrowck effect.
 566                 //
 567                 // FIXME: is above actually true? Do we want to track
 568                 // the fact that uninitialized data can be created via
 569                 // `NullOp::Box`?
 570             }
 571
 572             Rvalue::Aggregate(ref _aggregate_kind, ref operands) => {
 573                 for operand in operands {
 574                     self.consume_operand(context, Consume, (operand, span), flow_state);
 575                 }
 576             }
 577         }
 578     }
 579
 580     fn consume_operand(&mut self,
 581                        context: Context,
 582                        consume_via_drop: ConsumeKind,
 583                        (operand, span): (&Operand<'tcx>, Span),
 584                        flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 585         match *operand {
 586             Operand::Consume(ref lvalue) => {
 587                 self.consume_lvalue(context, consume_via_drop, (lvalue, span), flow_state)
 588             }
 589             Operand::Constant(_) => {}
 590         }
 591     }
 592
 593     fn consume_lvalue(&mut self,
 594                       context: Context,
 595                       consume_via_drop: ConsumeKind,
 596                       lvalue_span: (&Lvalue<'tcx>, Span),
 597                       flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 598         let lvalue = lvalue_span.0;
 599         let ty = lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
 600         let moves_by_default =
 601             self.fake_infer_ctxt.type_moves_by_default(self.param_env, ty, DUMMY_SP);
 602         if moves_by_default {
 603             // move of lvalue: check if this is move of already borrowed path
 604             self.access_lvalue(context, lvalue_span, (Deep, Write(WriteKind::Move)), flow_state);
 605         } else {
 606             // copy of lvalue: check if this is "copy of frozen path" (FIXME: see check_loans.rs)
 607             self.access_lvalue(context, lvalue_span, (Deep, Read(ReadKind::Copy)), flow_state);
 608         }
 609
 610         // Finally, check if path was already moved.
 611         match consume_via_drop {
 612             ConsumeKind::Drop => {
 613                 // If path is merely being dropped, then we'll already
 614                 // check the drop flag to see if it is moved (thus we
 615                 // skip this check in that case).
 616             }
 617             ConsumeKind::Consume => {
 618                 self.check_if_path_is_moved(context, "use", lvalue_span, flow_state);
 619             }
 620         }
 621     }
 622 }
 623
 624 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
 625     fn check_if_reassignment_to_immutable_state(&mut self,
 626                                                 context: Context,
 627                                                 (lvalue, span): (&Lvalue<'tcx>, Span),
 628                                                 flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 629         let move_data = self.move_data;
 630
 631         // determine if this path has a non-mut owner (and thus needs checking).
 632         let mut l = lvalue;
 633         loop {
 634             match *l {
 635                 Lvalue::Projection(ref proj) => {
 636                     l = &proj.base;
 637                     continue;
 638                 }
 639                 Lvalue::Local(local) => {
 640                     match self.mir.local_decls[local].mutability {
 641                         Mutability::Not => break, // needs check
 642                         Mutability::Mut => return,
 643                     }
 644                 }
 645                 Lvalue::Static(_) => {
 646                     // mutation of non-mut static is always illegal,
 647                     // independent of dataflow.
 648                     self.report_assignment_to_static(context, (lvalue, span));
 649                     return;
 650                 }
 651             }
 652         }
 653
 654         if let Some(mpi) = self.move_path_for_lvalue(lvalue) {
 655             if flow_state.inits.curr_state.contains(&mpi) {
 656                 // may already be assigned before reaching this statement;
 657                 // report error.
 658                 // FIXME: Not ideal, it only finds the assignment that lexically comes first
 659                 let assigned_lvalue = &move_data.move_paths[mpi].lvalue;
 660                 let assignment_stmt = self.mir.basic_blocks().iter().filter_map(|bb| {
 661                     bb.statements.iter().find(|stmt| {
 662                         if let StatementKind::Assign(ref lv, _) = stmt.kind {
 663                             *lv == *assigned_lvalue
 664                         } else {
 665                             false
 666                         }
 667                     })
 668                 }).next().unwrap();
 669                 self.report_illegal_reassignment(
 670                     context, (lvalue, span), assignment_stmt.source_info.span);
 671             }
 672         }
 673     }
 674
 675     fn check_if_path_is_moved(&mut self,
 676                               context: Context,
 677                               desired_action: &str,
 678                               lvalue_span: (&Lvalue<'tcx>, Span),
 679                               flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 680         // FIXME: analogous code in check_loans first maps `lvalue` to
 681         // its base_path ... but is that what we want here?
 682         let lvalue = self.base_path(lvalue_span.0);
 683
 684         let maybe_uninits = &flow_state.uninits;
 685         let curr_move_outs = &flow_state.move_outs.curr_state;
 686
 687         // Bad scenarios:
 688         //
 689         // 1. Move of `a.b.c`, use of `a.b.c`
 690         // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
 691         // 3. Move of `a.b.c`, use of `a` or `a.b`
 692         // 4. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
 693         //    partial initialization support, one might have `a.x`
 694         //    initialized but not `a.b`.
 695         //
 696         // OK scenarios:
 697         //
 698         // 5. Move of `a.b.c`, use of `a.b.d`
 699         // 6. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
 700         // 7. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
 701         //    must have been initialized for the use to be sound.
 702         // 8. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
 703
 704         // The dataflow tracks shallow prefixes distinctly (that is,
 705         // field-accesses on P distinctly from P itself), in order to
 706         // track substructure initialization separately from the whole
 707         // structure.
 708         //
 709         // E.g., when looking at (*a.b.c).d, if the closest prefix for
 710         // which we have a MovePath is `a.b`, then that means that the
 711         // initialization state of `a.b` is all we need to inspect to
 712         // know if `a.b.c` is valid (and from that we infer that the
 713         // dereference and `.d` access is also valid, since we assume
 714         // `a.b.c` is assigned a reference to a initialized and
 715         // well-formed record structure.)
 716
 717         // Therefore, if we seek out the *closest* prefix for which we
 718         // have a MovePath, that should capture the initialization
 719         // state for the lvalue scenario.
 720         //
 721         // This code covers scenarios 1, 2, and 4.
 722
 723         debug!("check_if_path_is_moved part1 lvalue: {:?}", lvalue);
 724         match self.move_path_closest_to(lvalue) {
 725             Ok(mpi) => {
 726                 if maybe_uninits.curr_state.contains(&mpi) {
 727                     self.report_use_of_moved_or_uninitialized(context, desired_action,
 728                                                               lvalue_span, mpi,
 729                                                               curr_move_outs);
 730                     return; // don't bother finding other problems.
 731                 }
 732             }
 733             Err(NoMovePathFound::ReachedStatic) => {
 734                 // Okay: we do not build MoveData for static variables
 735             }
 736
 737             // Only query longest prefix with a MovePath, not further
 738             // ancestors; dataflow recurs on children when parents
 739             // move (to support partial (re)inits).
 740             //
 741             // (I.e. querying parents breaks scenario 8; but may want
 742             // to do such a query based on partial-init feature-gate.)
 743         }
 744
 745         // A move of any shallow suffix of `lvalue` also interferes
 746         // with an attempt to use `lvalue`. This is scenario 3 above.
 747         //
 748         // (Distinct from handling of scenarios 1+2+4 above because
 749         // `lvalue` does not interfere with suffixes of its prefixes,
 750         // e.g. `a.b.c` does not interfere with `a.b.d`)
 751
 752         debug!("check_if_path_is_moved part2 lvalue: {:?}", lvalue);
 753         if let Some(mpi) = self.move_path_for_lvalue(lvalue) {
 754             if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) {
 755                 self.report_use_of_moved_or_uninitialized(context, desired_action,
 756                                                           lvalue_span, child_mpi,
 757                                                           curr_move_outs);
 758                 return; // don't bother finding other problems.
 759             }
 760         }
 761     }
 762
 763     /// Currently MoveData does not store entries for all lvalues in
 764     /// the input MIR. For example it will currently filter out
 765     /// lvalues that are Copy; thus we do not track lvalues of shared
 766     /// reference type. This routine will walk up an lvalue along its
 767     /// prefixes, searching for a foundational lvalue that *is*
 768     /// tracked in the MoveData.
 769     ///
 770     /// An Err result includes a tag indicated why the search failed.
 771     /// Currenly this can only occur if the lvalue is built off of a
 772     /// static variable, as we do not track those in the MoveData.
 773     fn move_path_closest_to(&mut self, lvalue: &Lvalue<'tcx>)
 774                             -> Result<MovePathIndex, NoMovePathFound>
 775     {
 776         let mut last_prefix = lvalue;
 777         for prefix in self.prefixes(lvalue, PrefixSet::All) {
 778             if let Some(mpi) = self.move_path_for_lvalue(prefix) {
 779                 return Ok(mpi);
 780             }
 781             last_prefix = prefix;
 782         }
 783         match *last_prefix {
 784             Lvalue::Local(_) => panic!("should have move path for every Local"),
 785             Lvalue::Projection(_) => panic!("PrefixSet::All meant dont stop for Projection"),
 786             Lvalue::Static(_) => return Err(NoMovePathFound::ReachedStatic),
 787         }
 788     }
 789
 790     fn move_path_for_lvalue(&mut self,
 791                             lvalue: &Lvalue<'tcx>)
 792                             -> Option<MovePathIndex>
 793     {
 794         // If returns None, then there is no move path corresponding
 795         // to a direct owner of `lvalue` (which means there is nothing
 796         // that borrowck tracks for its analysis).
 797
 798         match self.move_data.rev_lookup.find(lvalue) {
 799             LookupResult::Parent(_) => None,
 800             LookupResult::Exact(mpi) => Some(mpi),
 801         }
 802     }
 803
 804     fn check_if_assigned_path_is_moved(&mut self,
 805                                        context: Context,
 806                                        (lvalue, span): (&Lvalue<'tcx>, Span),
 807                                        flow_state: &InProgress<'b, 'gcx, 'tcx>) {
 808         // recur down lvalue; dispatch to check_if_path_is_moved when necessary
 809         let mut lvalue = lvalue;
 810         loop {
 811             match *lvalue {
 812                 Lvalue::Local(_) | Lvalue::Static(_) => {
 813                     // assigning to `x` does not require `x` be initialized.
 814                     break;
 815                 }
 816                 Lvalue::Projection(ref proj) => {
 817                     let Projection { ref base, ref elem } = **proj;
 818                     match *elem {
 819                         ProjectionElem::Deref |
 820                         // assigning to *P requires `P` initialized.
 821                         ProjectionElem::Index(_/*operand*/) |
 822                         ProjectionElem::ConstantIndex { .. } |
 823                         // assigning to P[i] requires `P` initialized.
 824                         ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
 825                         // assigning to (P->variant) is okay if assigning to `P` is okay
 826                         //
 827                         // FIXME: is this true even if P is a adt with a dtor?
 828                         { }
 829
 830                         ProjectionElem::Subslice { .. } => {
 831                             panic!("we dont allow assignments to subslices, context: {:?}",
 832                                    context);
 833                         }
 834
 835                         ProjectionElem::Field(..) => {
 836                             // if type of `P` has a dtor, then
 837                             // assigning to `P.f` requires `P` itself
 838                             // be already initialized
 839                             let tcx = self.tcx;
 840                             match base.ty(self.mir, tcx).to_ty(tcx).sty {
 841                                 ty::TyAdt(def, _) if def.has_dtor(tcx) => {
 842
 843                                     // FIXME: analogous code in
 844                                     // check_loans.rs first maps
 845                                     // `base` to its base_path.
 846
 847                                     self.check_if_path_is_moved(
 848                                         context, "assignment", (base, span), flow_state);
 849
 850                                     // (base initialized; no need to
 851                                     // recur further)
 852                                     break;
 853                                 }
 854                                 _ => {}
 855                             }
 856                         }
 857                     }
 858
 859                     lvalue = base;
 860                     continue;
 861                 }
 862             }
 863         }
 864     }
 865
 866     /// Check the permissions for the given lvalue and read or write kind
 867     fn check_access_permissions(&self, (lvalue, span): (&Lvalue<'tcx>, Span), kind: ReadOrWrite) {
 868         match kind {
 869             Write(WriteKind::MutableBorrow(BorrowKind::Unique)) => {
 870                 if let Err(_lvalue_err) = self.is_unique(lvalue) {
 871                     span_bug!(span, "&unique borrow for `{}` should not fail",
 872                         self.describe_lvalue(lvalue));
 873                 }
 874             },
 875             Write(WriteKind::MutableBorrow(BorrowKind::Mut)) => {
 876                 if let Err(lvalue_err) = self.is_mutable(lvalue) {
 877                     let mut err = self.tcx.cannot_borrow_path_as_mutable(span,
 878                         &format!("immutable item `{}`",
 879                                   self.describe_lvalue(lvalue)),
 880                         Origin::Mir);
 881                     err.span_label(span, "cannot borrow as mutable");
 882
 883                     if lvalue != lvalue_err {
 884                         err.note(&format!("Value not mutable causing this error: `{}`",
 885                             self.describe_lvalue(lvalue_err)));
 886                     }
 887
 888                     err.emit();
 889                 }
 890             },
 891             _ => {}// Access authorized
 892         }
 893     }
 894
 895     /// Can this value be written or borrowed mutably
 896     fn is_mutable<'d>(&self, lvalue: &'d Lvalue<'tcx>) -> Result<(), &'d Lvalue<'tcx>> {
 897         match *lvalue {
 898             Lvalue::Local(local) => {
 899                 let local = &self.mir.local_decls[local];
 900                 match local.mutability {
 901                     Mutability::Not => Err(lvalue),
 902                     Mutability::Mut => Ok(())
 903                 }
 904             },
 905             Lvalue::Static(ref static_) => {
 906                 if !self.tcx.is_static_mut(static_.def_id) {
 907                     Err(lvalue)
 908                 } else {
 909                     Ok(())
 910                 }
 911             },
 912             Lvalue::Projection(ref proj) => {
 913                 match proj.elem {
 914                     ProjectionElem::Deref => {
 915                         let base_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 916
 917                         // `Box<T>` owns its content, so mutable if its location is mutable
 918                         if base_ty.is_box() {
 919                             return self.is_mutable(&proj.base);
 920                         }
 921
 922                         // Otherwise we check the kind of deref to decide
 923                         match base_ty.sty {
 924                             ty::TyRef(_, tnm) => {
 925                                 match tnm.mutbl {
 926                                     // Shared borrowed data is never mutable
 927                                     hir::MutImmutable => Err(lvalue),
 928                                     // Mutably borrowed data is mutable, but only if we have a
 929                                     // unique path to the `&mut`
 930                                     hir::MutMutable => self.is_unique(&proj.base),
 931                                 }
 932                             },
 933                             ty::TyRawPtr(tnm) => {
 934                                 match tnm.mutbl {
 935                                     // `*const` raw pointers are not mutable
 936                                     hir::MutImmutable => Err(lvalue),
 937                                     // `*mut` raw pointers are always mutable, regardless of context
 938                                     // The users have to check by themselve.
 939                                     hir::MutMutable => Ok(()),
 940                                 }
 941                             },
 942                             // Deref should only be for reference, pointers or boxes
 943                             _ => bug!("Deref of unexpected type: {:?}", base_ty)
 944                         }
 945                     },
 946                     // All other projections are owned by their base path, so mutable if
 947                     // base path is mutable
 948                     ProjectionElem::Field(..) |
 949                     ProjectionElem::Index(..) |
 950                     ProjectionElem::ConstantIndex{..} |
 951                     ProjectionElem::Subslice{..} |
 952                     ProjectionElem::Downcast(..) =>
 953                         self.is_mutable(&proj.base)
 954                 }
 955             }
 956         }
 957     }
 958
 959     /// Does this lvalue have a unique path
 960     fn is_unique<'d>(&self, lvalue: &'d Lvalue<'tcx>) -> Result<(), &'d Lvalue<'tcx>> {
 961         match *lvalue {
 962             Lvalue::Local(..) => {
 963                 // Local variables are unique
 964                 Ok(())
 965             },
 966             Lvalue::Static(..) => {
 967                 // Static variables are not
 968                 Err(lvalue)
 969             },
 970             Lvalue::Projection(ref proj) => {
 971                 match proj.elem {
 972                     ProjectionElem::Deref => {
 973                         let base_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 974
 975                         // `Box<T>` referent is unique if box is a unique spot
 976                         if base_ty.is_box() {
 977                             return self.is_unique(&proj.base);
 978                         }
 979
 980                         // Otherwise we check the kind of deref to decide
 981                         match base_ty.sty {
 982                             ty::TyRef(_, tnm) => {
 983                                 match tnm.mutbl {
 984                                     // lvalue represent an aliased location
 985                                     hir::MutImmutable => Err(lvalue),
 986                                     // `&mut T` is as unique as the context in which it is found
 987                                     hir::MutMutable => self.is_unique(&proj.base),
 988                                 }
 989                             },
 990                             ty::TyRawPtr(tnm) => {
 991                                 match tnm.mutbl {
 992                                     // `*mut` can be aliased, but we leave it to user
 993                                     hir::MutMutable => Ok(()),
 994                                     // `*const` is treated the same as `*mut`
 995                                     hir::MutImmutable => Ok(()),
 996                                 }
 997                             },
 998                             // Deref should only be for reference, pointers or boxes
 999                             _ => bug!("Deref of unexpected type: {:?}", base_ty)
1000                         }
1001                     },
1002                     // Other projections are unique if the base is unique
1003                     ProjectionElem::Field(..) |
1004                     ProjectionElem::Index(..) |
1005                     ProjectionElem::ConstantIndex{..} |
1006                     ProjectionElem::Subslice{..} |
1007                     ProjectionElem::Downcast(..) =>
1008                         self.is_unique(&proj.base)
1009                 }
1010             }
1011         }
1012     }
1013 }
1014
1015 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1016 enum NoMovePathFound {
1017     ReachedStatic,
1018 }
1019
1020 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
1021     fn each_borrow_involving_path<F>(&mut self,
1022                                      _context: Context,
1023                                      access_lvalue: (ShallowOrDeep, &Lvalue<'tcx>),
1024                                      flow_state: &InProgress<'b, 'gcx, 'tcx>,
1025                                      mut op: F)
1026         where F: FnMut(&mut Self, BorrowIndex, &BorrowData<'tcx>, &Lvalue) -> Control
1027     {
1028         let (access, lvalue) = access_lvalue;
1029
1030         // FIXME: analogous code in check_loans first maps `lvalue` to
1031         // its base_path.
1032
1033         let domain = flow_state.borrows.base_results.operator();
1034         let data = domain.borrows();
1035
1036         // check for loan restricting path P being used. Accounts for
1037         // borrows of P, P.a.b, etc.
1038         'next_borrow: for i in flow_state.borrows.elems_incoming() {
1039             let borrowed = &data[i];
1040
1041             // Is `lvalue` (or a prefix of it) already borrowed? If
1042             // so, that's relevant.
1043             //
1044             // FIXME: Differs from AST-borrowck; includes drive-by fix
1045             // to #38899. Will probably need back-compat mode flag.
1046             for accessed_prefix in self.prefixes(lvalue, PrefixSet::All) {
1047                 if *accessed_prefix == borrowed.lvalue {
1048                     // FIXME: pass in enum describing case we are in?
1049                     let ctrl = op(self, i, borrowed, accessed_prefix);
1050                     if ctrl == Control::Break { return; }
1051                 }
1052             }
1053
1054             // Is `lvalue` a prefix (modulo access type) of the
1055             // `borrowed.lvalue`? If so, that's relevant.
1056
1057             let prefix_kind = match access {
1058                 Shallow(Some(ArtificialField::Discriminant)) |
1059                 Shallow(Some(ArtificialField::ArrayLength)) => {
1060                     // The discriminant and array length are like
1061                     // additional fields on the type; they do not
1062                     // overlap any existing data there. Furthermore,
1063                     // they cannot actually be a prefix of any
1064                     // borrowed lvalue (at least in MIR as it is
1065                     // currently.)
1066                     continue 'next_borrow;
1067                 }
1068                 Shallow(None) => PrefixSet::Shallow,
1069                 Deep => PrefixSet::Supporting,
1070             };
1071
1072             for borrowed_prefix in self.prefixes(&borrowed.lvalue, prefix_kind) {
1073                 if borrowed_prefix == lvalue {
1074                     // FIXME: pass in enum describing case we are in?
1075                     let ctrl = op(self, i, borrowed, borrowed_prefix);
1076                     if ctrl == Control::Break { return; }
1077                 }
1078             }
1079         }
1080     }
1081 }
1082
1083 use self::prefixes::PrefixSet;
1084
1085 /// From the NLL RFC: "The deep [aka 'supporting'] prefixes for an
1086 /// lvalue are formed by stripping away fields and derefs, except that
1087 /// we stop when we reach the deref of a shared reference. [...] "
1088 ///
1089 /// "Shallow prefixes are found by stripping away fields, but stop at
1090 /// any dereference. So: writing a path like `a` is illegal if `a.b`
1091 /// is borrowed. But: writing `a` is legal if `*a` is borrowed,
1092 /// whether or not `a` is a shared or mutable reference. [...] "
1093 mod prefixes {
1094     use super::{MirBorrowckCtxt};
1095
1096     use rustc::hir;
1097     use rustc::ty::{self, TyCtxt};
1098     use rustc::mir::{Lvalue, Mir, ProjectionElem};
1099
1100     pub trait IsPrefixOf<'tcx> {
1101         fn is_prefix_of(&self, other: &Lvalue<'tcx>) -> bool;
1102     }
1103
1104     impl<'tcx> IsPrefixOf<'tcx> for Lvalue<'tcx> {
1105         fn is_prefix_of(&self, other: &Lvalue<'tcx>) -> bool {
1106             let mut cursor = other;
1107             loop {
1108                 if self == cursor {
1109                     return true;
1110                 }
1111
1112                 match *cursor {
1113                     Lvalue::Local(_) |
1114                     Lvalue::Static(_) => return false,
1115                     Lvalue::Projection(ref proj) => {
1116                         cursor = &proj.base;
1117                     }
1118                 }
1119             }
1120         }
1121     }
1122
1123
1124     pub(super) struct Prefixes<'c, 'gcx: 'tcx, 'tcx: 'c> {
1125         mir: &'c Mir<'tcx>,
1126         tcx: TyCtxt<'c, 'gcx, 'tcx>,
1127         kind: PrefixSet,
1128         next: Option<&'c Lvalue<'tcx>>,
1129     }
1130
1131     #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1132     pub(super) enum PrefixSet {
1133         /// Doesn't stop until it returns the base case (a Local or
1134         /// Static prefix).
1135         All,
1136         /// Stops at any dereference.
1137         Shallow,
1138         /// Stops at the deref of a shared reference.
1139         Supporting,
1140     }
1141
1142     impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
1143         /// Returns an iterator over the prefixes of `lvalue`
1144         /// (inclusive) from longest to smallest, potentially
1145         /// terminating the iteration early based on `kind`.
1146         pub(super) fn prefixes<'d>(&self,
1147                                    lvalue: &'d Lvalue<'tcx>,
1148                                    kind: PrefixSet)
1149                                    -> Prefixes<'d, 'gcx, 'tcx> where 'b: 'd
1150         {
1151             Prefixes { next: Some(lvalue), kind, mir: self.mir, tcx: self.tcx }
1152         }
1153     }
1154
1155     impl<'c, 'gcx, 'tcx> Iterator for Prefixes<'c, 'gcx, 'tcx> {
1156         type Item = &'c Lvalue<'tcx>;
1157         fn next(&mut self) -> Option<Self::Item> {
1158             let mut cursor = match self.next {
1159                 None => return None,
1160                 Some(lvalue) => lvalue,
1161             };
1162
1163             // Post-processing `lvalue`: Enqueue any remaining
1164             // work. Also, `lvalue` may not be a prefix itself, but
1165             // may hold one further down (e.g. we never return
1166             // downcasts here, but may return a base of a downcast).
1167
1168             'cursor: loop {
1169                 let proj = match *cursor {
1170                     Lvalue::Local(_) | // search yielded this leaf
1171                     Lvalue::Static(_) => {
1172                         self.next = None;
1173                         return Some(cursor);
1174                     }
1175
1176                     Lvalue::Projection(ref proj) => proj,
1177                 };
1178
1179                 match proj.elem {
1180                     ProjectionElem::Field(_/*field*/, _/*ty*/) => {
1181                         // FIXME: add union handling
1182                         self.next = Some(&proj.base);
1183                         return Some(cursor);
1184                     }
1185                     ProjectionElem::Downcast(..) |
1186                     ProjectionElem::Subslice { .. } |
1187                     ProjectionElem::ConstantIndex { .. } |
1188                     ProjectionElem::Index(_) => {
1189                         cursor = &proj.base;
1190                         continue 'cursor;
1191                     }
1192                     ProjectionElem::Deref => {
1193                         // (handled below)
1194                     }
1195                 }
1196
1197                 assert_eq!(proj.elem, ProjectionElem::Deref);
1198
1199                 match self.kind {
1200                     PrefixSet::Shallow => {
1201                         // shallow prefixes are found by stripping away
1202                         // fields, but stop at *any* dereference.
1203                         // So we can just stop the traversal now.
1204                         self.next = None;
1205                         return Some(cursor);
1206                     }
1207                     PrefixSet::All => {
1208                         // all prefixes: just blindly enqueue the base
1209                         // of the projection
1210                         self.next = Some(&proj.base);
1211                         return Some(cursor);
1212                     }
1213                     PrefixSet::Supporting => {
1214                         // fall through!
1215                     }
1216                 }
1217
1218                 assert_eq!(self.kind, PrefixSet::Supporting);
1219                 // supporting prefixes: strip away fields and
1220                 // derefs, except we stop at the deref of a shared
1221                 // reference.
1222
1223                 let ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
1224                 match ty.sty {
1225                     ty::TyRawPtr(_) |
1226                     ty::TyRef(_/*rgn*/, ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
1227                         // don't continue traversing over derefs of raw pointers or shared borrows.
1228                         self.next = None;
1229                         return Some(cursor);
1230                     }
1231
1232                     ty::TyRef(_/*rgn*/, ty::TypeAndMut { ty: _, mutbl: hir::MutMutable }) => {
1233                         self.next = Some(&proj.base);
1234                         return Some(cursor);
1235                     }
1236
1237                     ty::TyAdt(..) if ty.is_box() => {
1238                         self.next = Some(&proj.base);
1239                         return Some(cursor);
1240                     }
1241
1242                     _ => panic!("unknown type fed to Projection Deref."),
1243                 }
1244             }
1245         }
1246     }
1247 }
1248
1249 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
1250     fn report_use_of_moved_or_uninitialized(&mut self,
1251                            _context: Context,
1252                            desired_action: &str,
1253                            (lvalue, span): (&Lvalue, Span),
1254                            mpi: MovePathIndex,
1255                            curr_move_out: &IdxSetBuf<MoveOutIndex>) {
1256
1257         let mois = self.move_data.path_map[mpi].iter().filter(
1258             |moi| curr_move_out.contains(moi)).collect::<Vec<_>>();
1259
1260         if mois.is_empty() {
1261             self.tcx.cannot_act_on_uninitialized_variable(span,
1262                                                           desired_action,
1263                                                           &self.describe_lvalue(lvalue),
1264                                                           Origin::Mir)
1265                     .span_label(span, format!("use of possibly uninitialized `{}`",
1266                                               self.describe_lvalue(lvalue)))
1267                     .emit();
1268         } else {
1269             let msg = ""; //FIXME: add "partially " or "collaterally "
1270
1271             let mut err = self.tcx.cannot_act_on_moved_value(span,
1272                                                              desired_action,
1273                                                              msg,
1274                                                              &self.describe_lvalue(lvalue),
1275                                                              Origin::Mir);
1276             err.span_label(span, format!("value {} here after move", desired_action));
1277             for moi in mois {
1278                 let move_msg = ""; //FIXME: add " (into closure)"
1279                 let move_span = self.mir.source_info(self.move_data.moves[*moi].source).span;
1280                 if span == move_span {
1281                     err.span_label(span,
1282                                    format!("value moved{} here in previous iteration of loop",
1283                                            move_msg));
1284                 } else {
1285                     err.span_label(move_span, format!("value moved{} here", move_msg));
1286                 };
1287             }
1288             //FIXME: add note for closure
1289             err.emit();
1290         }
1291     }
1292
1293     fn report_move_out_while_borrowed(&mut self,
1294                                       _context: Context,
1295                                       (lvalue, span): (&Lvalue, Span),
1296                                       borrow: &BorrowData) {
1297         self.tcx.cannot_move_when_borrowed(span,
1298                                            &self.describe_lvalue(lvalue),
1299                                            Origin::Mir)
1300                 .span_label(self.retrieve_borrow_span(borrow),
1301                             format!("borrow of `{}` occurs here",
1302                                     self.describe_lvalue(&borrow.lvalue)))
1303                 .span_label(span, format!("move out of `{}` occurs here",
1304                                           self.describe_lvalue(lvalue)))
1305                 .emit();
1306     }
1307
1308     fn report_use_while_mutably_borrowed(&mut self,
1309                                          _context: Context,
1310                                          (lvalue, span): (&Lvalue, Span),
1311                                          borrow : &BorrowData) {
1312
1313         let mut err = self.tcx.cannot_use_when_mutably_borrowed(
1314             span, &self.describe_lvalue(lvalue),
1315             self.retrieve_borrow_span(borrow), &self.describe_lvalue(&borrow.lvalue),
1316             Origin::Mir);
1317
1318         err.emit();
1319     }
1320
1321     /// Finds the span of arguments of a closure (within `maybe_closure_span`) and its usage of
1322     /// the local assigned at `location`.
1323     /// This is done by searching in statements succeeding `location`
1324     /// and originating from `maybe_closure_span`.
1325     fn find_closure_span(
1326         &self,
1327         maybe_closure_span: Span,
1328         location: Location,
1329     ) -> Option<(Span, Span)> {
1330         use rustc::hir::ExprClosure;
1331         use rustc::mir::AggregateKind;
1332
1333         let local = if let StatementKind::Assign(Lvalue::Local(local), _) =
1334             self.mir[location.block].statements[location.statement_index].kind
1335         {
1336             local
1337         } else {
1338             return None;
1339         };
1340
1341         for stmt in &self.mir[location.block].statements[location.statement_index + 1..] {
1342             if maybe_closure_span != stmt.source_info.span {
1343                 break;
1344             }
1345
1346             if let StatementKind::Assign(_, Rvalue::Aggregate(ref kind, ref lvs)) = stmt.kind {
1347                 if let AggregateKind::Closure(def_id, _) = **kind {
1348                     debug!("find_closure_span: found closure {:?}", lvs);
1349
1350                     return if let Some(node_id) = self.tcx.hir.as_local_node_id(def_id) {
1351                         let args_span = if let ExprClosure(_, _, _, span, _) =
1352                             self.tcx.hir.expect_expr(node_id).node
1353                         {
1354                             span
1355                         } else {
1356                             return None;
1357                         };
1358
1359                         self.tcx
1360                             .with_freevars(node_id, |freevars| {
1361                                 for (v, lv) in freevars.iter().zip(lvs) {
1362                                     if let Operand::Consume(Lvalue::Local(l)) = *lv {
1363                                         if local == l {
1364                                             debug!(
1365                                                 "find_closure_span: found captured local {:?}",
1366                                                 l
1367                                             );
1368                                             return Some(v.span);
1369                                         }
1370                                     }
1371                                 }
1372                                 None
1373                             })
1374                             .map(|var_span| (args_span, var_span))
1375                     } else {
1376                         None
1377                     };
1378                 }
1379             }
1380         }
1381
1382         None
1383     }
1384
1385     fn report_conflicting_borrow(&mut self,
1386                                  context: Context,
1387                                  common_prefix: &Lvalue,
1388                                  (lvalue, span): (&Lvalue, Span),
1389                                  gen_borrow_kind: BorrowKind,
1390                                  issued_borrow: &BorrowData,
1391                                  end_issued_loan_span: Option<Span>) {
1392         use self::prefixes::IsPrefixOf;
1393
1394         assert!(common_prefix.is_prefix_of(lvalue));
1395         assert!(common_prefix.is_prefix_of(&issued_borrow.lvalue));
1396
1397         let issued_span = self.retrieve_borrow_span(issued_borrow);
1398
1399         let new_closure_span = self.find_closure_span(span, context.loc);
1400         let span = new_closure_span.map(|(args, _)| args).unwrap_or(span);
1401         let old_closure_span = self.find_closure_span(issued_span, issued_borrow.location);
1402         let issued_span = old_closure_span.map(|(args, _)| args).unwrap_or(issued_span);
1403
1404         let desc_lvalue = self.describe_lvalue(lvalue);
1405
1406         // FIXME: supply non-"" `opt_via` when appropriate
1407         let mut err = match (gen_borrow_kind, "immutable", "mutable",
1408                              issued_borrow.kind, "immutable", "mutable") {
1409             (BorrowKind::Shared, lft, _, BorrowKind::Mut, _, rgt) |
1410             (BorrowKind::Mut, _, lft, BorrowKind::Shared, rgt, _) =>
1411                 self.tcx.cannot_reborrow_already_borrowed(
1412                     span, &desc_lvalue, "", lft, issued_span,
1413                     "it", rgt, "", end_issued_loan_span, Origin::Mir),
1414
1415             (BorrowKind::Mut, _, _, BorrowKind::Mut, _, _) =>
1416                 self.tcx.cannot_mutably_borrow_multiply(
1417                     span, &desc_lvalue, "", issued_span,
1418                     "", end_issued_loan_span, Origin::Mir),
1419
1420             (BorrowKind::Unique, _, _, BorrowKind::Unique, _, _) =>
1421                 self.tcx.cannot_uniquely_borrow_by_two_closures(
1422                     span, &desc_lvalue, issued_span,
1423                     end_issued_loan_span, Origin::Mir),
1424
1425             (BorrowKind::Unique, _, _, _, _, _) =>
1426                 self.tcx.cannot_uniquely_borrow_by_one_closure(
1427                     span, &desc_lvalue, "",
1428                     issued_span, "it", "", end_issued_loan_span, Origin::Mir),
1429
1430             (_, _, _, BorrowKind::Unique, _, _) =>
1431                 self.tcx.cannot_reborrow_already_uniquely_borrowed(
1432                     span, &desc_lvalue, "it", "",
1433                     issued_span, "", end_issued_loan_span, Origin::Mir),
1434
1435             (BorrowKind::Shared, _, _, BorrowKind::Shared, _, _) =>
1436                 unreachable!(),
1437         };
1438
1439         if let Some((_, var_span)) = old_closure_span {
1440             err.span_label(
1441                 var_span,
1442                 format!("previous borrow occurs due to use of `{}` in closure", desc_lvalue),
1443             );
1444         }
1445
1446         if let Some((_, var_span)) = new_closure_span {
1447             err.span_label(
1448                 var_span,
1449                 format!("borrow occurs due to use of `{}` in closure", desc_lvalue),
1450             );
1451         }
1452
1453         err.emit();
1454     }
1455
1456     fn report_illegal_mutation_of_borrowed(&mut self,
1457                                            _: Context,
1458                                            (lvalue, span): (&Lvalue, Span),
1459                                            loan: &BorrowData) {
1460         let mut err = self.tcx.cannot_assign_to_borrowed(
1461             span, self.retrieve_borrow_span(loan), &self.describe_lvalue(lvalue), Origin::Mir);
1462
1463         err.emit();
1464     }
1465
1466     fn report_illegal_reassignment(&mut self,
1467                                    _context: Context,
1468                                    (lvalue, span): (&Lvalue, Span),
1469                                    assigned_span: Span) {
1470         self.tcx.cannot_reassign_immutable(span,
1471                                            &self.describe_lvalue(lvalue),
1472                                            Origin::Mir)
1473                 .span_label(span, "cannot assign twice to immutable variable")
1474                 .span_label(assigned_span, format!("first assignment to `{}`",
1475                                                    self.describe_lvalue(lvalue)))
1476                 .emit();
1477     }
1478
1479     fn report_assignment_to_static(&mut self, _context: Context, (lvalue, span): (&Lvalue, Span)) {
1480         let mut err = self.tcx.cannot_assign_static(
1481             span, &self.describe_lvalue(lvalue), Origin::Mir);
1482         err.emit();
1483     }
1484 }
1485
1486 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
1487     // End-user visible description of `lvalue`
1488     fn describe_lvalue(&self, lvalue: &Lvalue) -> String {
1489         let mut buf = String::new();
1490         self.append_lvalue_to_string(lvalue, &mut buf, None);
1491         buf
1492     }
1493
1494     // Appends end-user visible description of `lvalue` to `buf`.
1495     fn append_lvalue_to_string(&self, lvalue: &Lvalue, buf: &mut String, autoderef: Option<bool>) {
1496         match *lvalue {
1497             Lvalue::Local(local) => {
1498                 self.append_local_to_string(local, buf, "_");
1499             }
1500             Lvalue::Static(ref static_) => {
1501                 buf.push_str(&format!("{}", &self.tcx.item_name(static_.def_id)));
1502             }
1503             Lvalue::Projection(ref proj) => {
1504                 let mut autoderef = autoderef.unwrap_or(false);
1505                 let (prefix, suffix, index_operand) = match proj.elem {
1506                     ProjectionElem::Deref => {
1507                         if autoderef {
1508                             ("", format!(""), None)
1509                         } else {
1510                             ("(*", format!(")"), None)
1511                         }
1512                     },
1513                     ProjectionElem::Downcast(..) =>
1514                         ("",   format!(""), None), // (dont emit downcast info)
1515                     ProjectionElem::Field(field, _ty) => {
1516                         autoderef = true;
1517                         ("", format!(".{}", self.describe_field(&proj.base, field.index())), None)
1518                     },
1519                     ProjectionElem::Index(index) => {
1520                         autoderef = true;
1521                         ("",   format!(""), Some(index))
1522                     },
1523                     ProjectionElem::ConstantIndex { .. } | ProjectionElem::Subslice { .. } => {
1524                         autoderef = true;
1525                         // Since it isn't possible to borrow an element on a particular index and
1526                         // then use another while the borrow is held, don't output indices details
1527                         // to avoid confusing the end-user
1528                         ("",   format!("[..]"), None)
1529                     },
1530                 };
1531                 buf.push_str(prefix);
1532                 self.append_lvalue_to_string(&proj.base, buf, Some(autoderef));
1533                 if let Some(index) = index_operand {
1534                     buf.push_str("[");
1535                     self.append_local_to_string(index, buf, "..");
1536                     buf.push_str("]");
1537                 } else {
1538                     buf.push_str(&suffix);
1539                 }
1540             }
1541         }
1542     }
1543
1544     // Appends end-user visible description of the `local` lvalue to `buf`. If `local` doesn't have
1545     // a name, then `none_string` is appended instead
1546     fn append_local_to_string(&self, local_index: Local, buf: &mut String, none_string: &str) {
1547         let local = &self.mir.local_decls[local_index];
1548         match local.name {
1549             Some(name) => buf.push_str(&format!("{}", name)),
1550             None => buf.push_str(none_string)
1551         }
1552     }
1553
1554     // End-user visible description of the `field_index`nth field of `base`
1555     fn describe_field(&self, base: &Lvalue, field_index: usize) -> String {
1556         match *base {
1557             Lvalue::Local(local) => {
1558                 let local = &self.mir.local_decls[local];
1559                 self.describe_field_from_ty(&local.ty, field_index)
1560             },
1561             Lvalue::Static(ref static_) => {
1562                 self.describe_field_from_ty(&static_.ty, field_index)
1563             },
1564             Lvalue::Projection(ref proj) => {
1565                 match proj.elem {
1566                     ProjectionElem::Deref =>
1567                         self.describe_field(&proj.base, field_index),
1568                     ProjectionElem::Downcast(def, variant_index) =>
1569                         format!("{}", def.variants[variant_index].fields[field_index].name),
1570                     ProjectionElem::Field(_, field_type) =>
1571                         self.describe_field_from_ty(&field_type, field_index),
1572                     ProjectionElem::Index(..)
1573                     | ProjectionElem::ConstantIndex { .. }
1574                     | ProjectionElem::Subslice { .. } =>
1575                         format!("{}", self.describe_field(&proj.base, field_index)),
1576                 }
1577             }
1578         }
1579     }
1580
1581     // End-user visible description of the `field_index`nth field of `ty`
1582     fn describe_field_from_ty(&self, ty: &ty::Ty, field_index: usize) -> String {
1583         if ty.is_box() {
1584             // If the type is a box, the field is described from the boxed type
1585             self.describe_field_from_ty(&ty.boxed_ty(), field_index)
1586         }
1587         else {
1588             match ty.sty {
1589                 ty::TyAdt(def, _) => {
1590                     if def.is_enum() {
1591                         format!("{}", field_index)
1592                     }
1593                     else {
1594                         format!("{}", def.struct_variant().fields[field_index].name)
1595                     }
1596                 },
1597                 ty::TyTuple(_, _) => {
1598                     format!("{}", field_index)
1599                 },
1600                 ty::TyRef(_, tnm) | ty::TyRawPtr(tnm) => {
1601                     self.describe_field_from_ty(&tnm.ty, field_index)
1602                 },
1603                 ty::TyArray(ty, _) | ty::TySlice(ty) => {
1604                     self.describe_field_from_ty(&ty, field_index)
1605                 }
1606                 _ => {
1607                     // Might need a revision when the fields in trait RFC is implemented
1608                     // (https://github.com/rust-lang/rfcs/pull/1546)
1609                     bug!("End-user description not implemented for field access on `{:?}`", ty.sty);
1610                 }
1611             }
1612         }
1613     }
1614
1615     // Retrieve span of given borrow from the current MIR representation
1616     fn retrieve_borrow_span(&self, borrow: &BorrowData) -> Span {
1617         self.mir.source_info(borrow.location).span
1618     }
1619 }
1620
1621 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
1622     // FIXME (#16118): function intended to allow the borrow checker
1623     // to be less precise in its handling of Box while still allowing
1624     // moves out of a Box. They should be removed when/if we stop
1625     // treating Box specially (e.g. when/if DerefMove is added...)
1626
1627     fn base_path<'d>(&self, lvalue: &'d Lvalue<'tcx>) -> &'d Lvalue<'tcx> {
1628         //! Returns the base of the leftmost (deepest) dereference of an
1629         //! Box in `lvalue`. If there is no dereference of an Box
1630         //! in `lvalue`, then it just returns `lvalue` itself.
1631
1632         let mut cursor = lvalue;
1633         let mut deepest = lvalue;
1634         loop {
1635             let proj = match *cursor {
1636                 Lvalue::Local(..) | Lvalue::Static(..) => return deepest,
1637                 Lvalue::Projection(ref proj) => proj,
1638             };
1639             if proj.elem == ProjectionElem::Deref &&
1640                 lvalue.ty(self.mir, self.tcx).to_ty(self.tcx).is_box()
1641             {
1642                 deepest = &proj.base;
1643             }
1644             cursor = &proj.base;
1645         }
1646     }
1647 }
1648
1649 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1650 struct Context {
1651     kind: ContextKind,
1652     loc: Location,
1653 }
1654
1655 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1656 enum ContextKind {
1657     AssignLhs,
1658     AssignRhs,
1659     SetDiscrim,
1660     InlineAsm,
1661     SwitchInt,
1662     Drop,
1663     DropAndReplace,
1664     CallOperator,
1665     CallOperand,
1666     CallDest,
1667     Assert,
1668     Yield,
1669     StorageDead,
1670 }
1671
1672 impl ContextKind {
1673     fn new(self, loc: Location) -> Context { Context { kind: self, loc: loc } }
1674 }
1675
1676 impl<'b, 'gcx, 'tcx> InProgress<'b, 'gcx, 'tcx> {
1677     pub(super) fn new(borrows: DataflowResults<Borrows<'b, 'gcx, 'tcx>>,
1678                       inits: DataflowResults<MaybeInitializedLvals<'b, 'gcx, 'tcx>>,
1679                       uninits: DataflowResults<MaybeUninitializedLvals<'b, 'gcx, 'tcx>>,
1680                       move_out: DataflowResults<MovingOutStatements<'b, 'gcx, 'tcx>>)
1681                       -> Self {
1682         InProgress {
1683             borrows: FlowInProgress::new(borrows),
1684             inits: FlowInProgress::new(inits),
1685             uninits: FlowInProgress::new(uninits),
1686             move_outs: FlowInProgress::new(move_out)
1687         }
1688     }
1689
1690     fn each_flow<XB, XI, XU, XM>(&mut self,
1691                                  mut xform_borrows: XB,
1692                                  mut xform_inits: XI,
1693                                  mut xform_uninits: XU,
1694                                  mut xform_move_outs: XM) where
1695         XB: FnMut(&mut FlowInProgress<Borrows<'b, 'gcx, 'tcx>>),
1696         XI: FnMut(&mut FlowInProgress<MaybeInitializedLvals<'b, 'gcx, 'tcx>>),
1697         XU: FnMut(&mut FlowInProgress<MaybeUninitializedLvals<'b, 'gcx, 'tcx>>),
1698         XM: FnMut(&mut FlowInProgress<MovingOutStatements<'b, 'gcx, 'tcx>>),
1699     {
1700         xform_borrows(&mut self.borrows);
1701         xform_inits(&mut self.inits);
1702         xform_uninits(&mut self.uninits);
1703         xform_move_outs(&mut self.move_outs);
1704     }
1705
1706     fn summary(&self) -> String {
1707         let mut s = String::new();
1708
1709         s.push_str("borrows in effect: [");
1710         let mut saw_one = false;
1711         self.borrows.each_state_bit(|borrow| {
1712             if saw_one { s.push_str(", "); };
1713             saw_one = true;
1714             let borrow_data = &self.borrows.base_results.operator().borrows()[borrow];
1715             s.push_str(&format!("{}", borrow_data));
1716         });
1717         s.push_str("] ");
1718
1719         s.push_str("borrows generated: [");
1720         let mut saw_one = false;
1721         self.borrows.each_gen_bit(|borrow| {
1722             if saw_one { s.push_str(", "); };
1723             saw_one = true;
1724             let borrow_data = &self.borrows.base_results.operator().borrows()[borrow];
1725             s.push_str(&format!("{}", borrow_data));
1726         });
1727         s.push_str("] ");
1728
1729         s.push_str("inits: [");
1730         let mut saw_one = false;
1731         self.inits.each_state_bit(|mpi_init| {
1732             if saw_one { s.push_str(", "); };
1733             saw_one = true;
1734             let move_path =
1735                 &self.inits.base_results.operator().move_data().move_paths[mpi_init];
1736             s.push_str(&format!("{}", move_path));
1737         });
1738         s.push_str("] ");
1739
1740         s.push_str("uninits: [");
1741         let mut saw_one = false;
1742         self.uninits.each_state_bit(|mpi_uninit| {
1743             if saw_one { s.push_str(", "); };
1744             saw_one = true;
1745             let move_path =
1746                 &self.uninits.base_results.operator().move_data().move_paths[mpi_uninit];
1747             s.push_str(&format!("{}", move_path));
1748         });
1749         s.push_str("] ");
1750
1751         s.push_str("move_out: [");
1752         let mut saw_one = false;
1753         self.move_outs.each_state_bit(|mpi_move_out| {
1754             if saw_one { s.push_str(", "); };
1755             saw_one = true;
1756             let move_out =
1757                 &self.move_outs.base_results.operator().move_data().moves[mpi_move_out];
1758             s.push_str(&format!("{:?}", move_out));
1759         });
1760         s.push_str("]");
1761
1762         return s;
1763     }
1764 }
1765
1766 impl<'b, 'gcx, 'tcx> FlowInProgress<MaybeUninitializedLvals<'b, 'gcx, 'tcx>> {
1767     fn has_any_child_of(&self, mpi: MovePathIndex) -> Option<MovePathIndex> {
1768         let move_data = self.base_results.operator().move_data();
1769
1770         let mut todo = vec![mpi];
1771         let mut push_siblings = false; // don't look at siblings of original `mpi`.
1772         while let Some(mpi) = todo.pop() {
1773             if self.curr_state.contains(&mpi) {
1774                 return Some(mpi);
1775             }
1776             let move_path = &move_data.move_paths[mpi];
1777             if let Some(child) = move_path.first_child {
1778                 todo.push(child);
1779             }
1780             if push_siblings {
1781                 if let Some(sibling) = move_path.next_sibling {
1782                     todo.push(sibling);
1783                 }
1784             } else {
1785                 // after we've processed the original `mpi`, we should
1786                 // always traverse the siblings of any of its
1787                 // children.
1788                 push_siblings = true;
1789             }
1790         }
1791         return None;
1792     }
1793 }
1794
1795 impl<BD> FlowInProgress<BD> where BD: BitDenotation {
1796     fn each_state_bit<F>(&self, f: F) where F: FnMut(BD::Idx) {
1797         self.curr_state.each_bit(self.base_results.operator().bits_per_block(), f)
1798     }
1799
1800     fn each_gen_bit<F>(&self, f: F) where F: FnMut(BD::Idx) {
1801         self.stmt_gen.each_bit(self.base_results.operator().bits_per_block(), f)
1802     }
1803
1804     fn new(results: DataflowResults<BD>) -> Self {
1805         let bits_per_block = results.sets().bits_per_block();
1806         let curr_state = IdxSetBuf::new_empty(bits_per_block);
1807         let stmt_gen = IdxSetBuf::new_empty(bits_per_block);
1808         let stmt_kill = IdxSetBuf::new_empty(bits_per_block);
1809         FlowInProgress {
1810             base_results: results,
1811             curr_state: curr_state,
1812             stmt_gen: stmt_gen,
1813             stmt_kill: stmt_kill,
1814         }
1815     }
1816
1817     fn reset_to_entry_of(&mut self, bb: BasicBlock) {
1818         (*self.curr_state).clone_from(self.base_results.sets().on_entry_set_for(bb.index()));
1819     }
1820
1821     fn reconstruct_statement_effect(&mut self, loc: Location) {
1822         self.stmt_gen.reset_to_empty();
1823         self.stmt_kill.reset_to_empty();
1824         let mut ignored = IdxSetBuf::new_empty(0);
1825         let mut sets = BlockSets {
1826             on_entry: &mut ignored, gen_set: &mut self.stmt_gen, kill_set: &mut self.stmt_kill,
1827         };
1828         self.base_results.operator().statement_effect(&mut sets, loc);
1829     }
1830
1831     fn reconstruct_terminator_effect(&mut self, loc: Location) {
1832         self.stmt_gen.reset_to_empty();
1833         self.stmt_kill.reset_to_empty();
1834         let mut ignored = IdxSetBuf::new_empty(0);
1835         let mut sets = BlockSets {
1836             on_entry: &mut ignored, gen_set: &mut self.stmt_gen, kill_set: &mut self.stmt_kill,
1837         };
1838         self.base_results.operator().terminator_effect(&mut sets, loc);
1839     }
1840
1841     fn apply_local_effect(&mut self) {
1842         self.curr_state.union(&self.stmt_gen);
1843         self.curr_state.subtract(&self.stmt_kill);
1844     }
1845
1846     fn elems_incoming(&self) -> indexed_set::Elems<BD::Idx> {
1847         let univ = self.base_results.sets().bits_per_block();
1848         self.curr_state.elems(univ)
1849     }
1850 }