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