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