src/librustc_mir/borrow_check/mod.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 borrow_check::nll::region_infer::RegionInferenceContext;
  14 use rustc::hir;
  15 use rustc::hir::Node;
  16 use rustc::hir::def_id::DefId;
  17 use rustc::infer::InferCtxt;
  18 use rustc::lint::builtin::UNUSED_MUT;
  19 use rustc::middle::borrowck::SignalledError;
  20 use rustc::mir::{AggregateKind, BasicBlock, BorrowCheckResult, BorrowKind};
  21 use rustc::mir::{ClearCrossCrate, Local, Location, Mir, Mutability, Operand, Place};
  22 use rustc::mir::{Field, Projection, ProjectionElem, Rvalue, Statement, StatementKind};
  23 use rustc::mir::{Terminator, TerminatorKind};
  24 use rustc::ty::query::Providers;
  25 use rustc::ty::{self, TyCtxt};
  26
  27 use rustc_errors::{Applicability, Diagnostic, DiagnosticBuilder, Level};
  28 use rustc_data_structures::bit_set::BitSet;
  29 use rustc_data_structures::fx::FxHashSet;
  30 use rustc_data_structures::graph::dominators::Dominators;
  31 use smallvec::SmallVec;
  32
  33 use std::rc::Rc;
  34 use std::collections::BTreeMap;
  35
  36 use syntax_pos::Span;
  37
  38 use dataflow::indexes::{BorrowIndex, InitIndex, MoveOutIndex, MovePathIndex};
  39 use dataflow::move_paths::{HasMoveData, LookupResult, MoveData, MoveError};
  40 use dataflow::Borrows;
  41 use dataflow::DataflowResultsConsumer;
  42 use dataflow::FlowAtLocation;
  43 use dataflow::MoveDataParamEnv;
  44 use dataflow::{do_dataflow, DebugFormatted};
  45 use dataflow::EverInitializedPlaces;
  46 use dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
  47 use util::borrowck_errors::{BorrowckErrors, Origin};
  48
  49 use self::borrow_set::{BorrowData, BorrowSet};
  50 use self::flows::Flows;
  51 use self::location::LocationTable;
  52 use self::prefixes::PrefixSet;
  53 use self::MutateMode::{JustWrite, WriteAndRead};
  54 use self::mutability_errors::AccessKind;
  55
  56 use self::path_utils::*;
  57
  58 crate mod borrow_set;
  59 mod error_reporting;
  60 mod flows;
  61 mod location;
  62 mod move_errors;
  63 mod mutability_errors;
  64 mod path_utils;
  65 crate mod place_ext;
  66 mod places_conflict;
  67 mod prefixes;
  68 mod used_muts;
  69
  70 pub(crate) mod nll;
  71
  72 pub fn provide(providers: &mut Providers) {
  73     *providers = Providers {
  74         mir_borrowck,
  75         ..*providers
  76     };
  77 }
  78
  79 fn mir_borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> BorrowCheckResult<'tcx> {
  80     let input_mir = tcx.mir_validated(def_id);
  81     debug!("run query mir_borrowck: {}", tcx.item_path_str(def_id));
  82
  83     let mut return_early;
  84
  85     // Return early if we are not supposed to use MIR borrow checker for this function.
  86     return_early = !tcx.has_attr(def_id, "rustc_mir") && !tcx.use_mir_borrowck();
  87
  88     if tcx.is_struct_constructor(def_id) {
  89         // We are not borrow checking the automatically generated struct constructors
  90         // because we want to accept structs such as this (taken from the `linked-hash-map`
  91         // crate):
  92         // ```rust
  93         // struct Qey<Q: ?Sized>(Q);
  94         // ```
  95         // MIR of this struct constructor looks something like this:
  96         // ```rust
  97         // fn Qey(_1: Q) -> Qey<Q>{
  98         //     let mut _0: Qey<Q>;                  // return place
  99         //
 100         //     bb0: {
 101         //         (_0.0: Q) = move _1;             // bb0[0]: scope 0 at src/main.rs:1:1: 1:26
 102         //         return;                          // bb0[1]: scope 0 at src/main.rs:1:1: 1:26
 103         //     }
 104         // }
 105         // ```
 106         // The problem here is that `(_0.0: Q) = move _1;` is valid only if `Q` is
 107         // of statically known size, which is not known to be true because of the
 108         // `Q: ?Sized` constraint. However, it is true because the constructor can be
 109         // called only when `Q` is of statically known size.
 110         return_early = true;
 111     }
 112
 113     if return_early {
 114         return BorrowCheckResult {
 115             closure_requirements: None,
 116             used_mut_upvars: SmallVec::new(),
 117         };
 118     }
 119
 120     let opt_closure_req = tcx.infer_ctxt().enter(|infcx| {
 121         let input_mir: &Mir = &input_mir.borrow();
 122         do_mir_borrowck(&infcx, input_mir, def_id)
 123     });
 124     debug!("mir_borrowck done");
 125
 126     opt_closure_req
 127 }
 128
 129 fn do_mir_borrowck<'a, 'gcx, 'tcx>(
 130     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 131     input_mir: &Mir<'gcx>,
 132     def_id: DefId,
 133 ) -> BorrowCheckResult<'gcx> {
 134     debug!("do_mir_borrowck(def_id = {:?})", def_id);
 135
 136     let tcx = infcx.tcx;
 137     let attributes = tcx.get_attrs(def_id);
 138     let param_env = tcx.param_env(def_id);
 139     let id = tcx
 140         .hir()
 141         .as_local_node_id(def_id)
 142         .expect("do_mir_borrowck: non-local DefId");
 143
 144     // Replace all regions with fresh inference variables. This
 145     // requires first making our own copy of the MIR. This copy will
 146     // be modified (in place) to contain non-lexical lifetimes. It
 147     // will have a lifetime tied to the inference context.
 148     let mut mir: Mir<'tcx> = input_mir.clone();
 149     let free_regions = nll::replace_regions_in_mir(infcx, def_id, param_env, &mut mir);
 150     let mir = &mir; // no further changes
 151     let location_table = &LocationTable::new(mir);
 152
 153     let mut errors_buffer = Vec::new();
 154     let (move_data, move_errors): (MoveData<'tcx>, Option<Vec<(Place<'tcx>, MoveError<'tcx>)>>) =
 155         match MoveData::gather_moves(mir, tcx) {
 156             Ok(move_data) => (move_data, None),
 157             Err((move_data, move_errors)) => (move_data, Some(move_errors)),
 158         };
 159
 160     let mdpe = MoveDataParamEnv {
 161         move_data: move_data,
 162         param_env: param_env,
 163     };
 164
 165     let dead_unwinds = BitSet::new_empty(mir.basic_blocks().len());
 166     let mut flow_inits = FlowAtLocation::new(do_dataflow(
 167         tcx,
 168         mir,
 169         id,
 170         &attributes,
 171         &dead_unwinds,
 172         MaybeInitializedPlaces::new(tcx, mir, &mdpe),
 173         |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
 174     ));
 175
 176     let locals_are_invalidated_at_exit = match tcx.hir().body_owner_kind(id) {
 177             hir::BodyOwnerKind::Const | hir::BodyOwnerKind::Static(_) => false,
 178             hir::BodyOwnerKind::Fn => true,
 179     };
 180     let borrow_set = Rc::new(BorrowSet::build(
 181             tcx, mir, locals_are_invalidated_at_exit, &mdpe.move_data));
 182
 183     // If we are in non-lexical mode, compute the non-lexical lifetimes.
 184     let (regioncx, polonius_output, opt_closure_req) = nll::compute_regions(
 185         infcx,
 186         def_id,
 187         free_regions,
 188         mir,
 189         location_table,
 190         param_env,
 191         &mut flow_inits,
 192         &mdpe.move_data,
 193         &borrow_set,
 194         &mut errors_buffer,
 195     );
 196
 197     // The various `flow_*` structures can be large. We drop `flow_inits` here
 198     // so it doesn't overlap with the others below. This reduces peak memory
 199     // usage significantly on some benchmarks.
 200     drop(flow_inits);
 201
 202     let regioncx = Rc::new(regioncx);
 203
 204     let flow_borrows = FlowAtLocation::new(do_dataflow(
 205         tcx,
 206         mir,
 207         id,
 208         &attributes,
 209         &dead_unwinds,
 210         Borrows::new(tcx, mir, regioncx.clone(), &borrow_set),
 211         |rs, i| DebugFormatted::new(&rs.location(i)),
 212     ));
 213     let flow_uninits = FlowAtLocation::new(do_dataflow(
 214         tcx,
 215         mir,
 216         id,
 217         &attributes,
 218         &dead_unwinds,
 219         MaybeUninitializedPlaces::new(tcx, mir, &mdpe),
 220         |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
 221     ));
 222     let flow_ever_inits = FlowAtLocation::new(do_dataflow(
 223         tcx,
 224         mir,
 225         id,
 226         &attributes,
 227         &dead_unwinds,
 228         EverInitializedPlaces::new(tcx, mir, &mdpe),
 229         |bd, i| DebugFormatted::new(&bd.move_data().inits[i]),
 230     ));
 231
 232     let movable_generator = match tcx.hir().get(id) {
 233         Node::Expr(&hir::Expr {
 234             node: hir::ExprKind::Closure(.., Some(hir::GeneratorMovability::Static)),
 235             ..
 236         }) => false,
 237         _ => true,
 238     };
 239
 240     let dominators = mir.dominators();
 241
 242     let mut mbcx = MirBorrowckCtxt {
 243         infcx,
 244         mir,
 245         mir_def_id: def_id,
 246         move_data: &mdpe.move_data,
 247         location_table,
 248         movable_generator,
 249         locals_are_invalidated_at_exit,
 250         access_place_error_reported: Default::default(),
 251         reservation_error_reported: Default::default(),
 252         move_error_reported: BTreeMap::new(),
 253         uninitialized_error_reported: Default::default(),
 254         errors_buffer,
 255         nonlexical_regioncx: regioncx,
 256         used_mut: Default::default(),
 257         used_mut_upvars: SmallVec::new(),
 258         borrow_set,
 259         dominators,
 260     };
 261
 262     let mut state = Flows::new(
 263         flow_borrows,
 264         flow_uninits,
 265         flow_ever_inits,
 266         polonius_output,
 267     );
 268
 269     if let Some(errors) = move_errors {
 270         mbcx.report_move_errors(errors);
 271     }
 272     mbcx.analyze_results(&mut state); // entry point for DataflowResultsConsumer
 273
 274     // For each non-user used mutable variable, check if it's been assigned from
 275     // a user-declared local. If so, then put that local into the used_mut set.
 276     // Note that this set is expected to be small - only upvars from closures
 277     // would have a chance of erroneously adding non-user-defined mutable vars
 278     // to the set.
 279     let temporary_used_locals: FxHashSet<Local> = mbcx.used_mut.iter()
 280         .filter(|&local| mbcx.mir.local_decls[*local].is_user_variable.is_none())
 281         .cloned()
 282         .collect();
 283     // For the remaining unused locals that are marked as mutable, we avoid linting any that
 284     // were never initialized. These locals may have been removed as unreachable code; or will be
 285     // linted as unused variables.
 286     let unused_mut_locals = mbcx.mir.mut_vars_iter()
 287         .filter(|local| !mbcx.used_mut.contains(local))
 288         .collect();
 289     mbcx.gather_used_muts(temporary_used_locals, unused_mut_locals);
 290
 291     debug!("mbcx.used_mut: {:?}", mbcx.used_mut);
 292     let used_mut = mbcx.used_mut;
 293     for local in mbcx.mir.mut_vars_and_args_iter().filter(|local| !used_mut.contains(local)) {
 294         if let ClearCrossCrate::Set(ref vsi) = mbcx.mir.source_scope_local_data {
 295             let local_decl = &mbcx.mir.local_decls[local];
 296
 297             // Skip implicit `self` argument for closures
 298             if local.index() == 1 && tcx.is_closure(mbcx.mir_def_id) {
 299                 continue;
 300             }
 301
 302             // Skip over locals that begin with an underscore or have no name
 303             match local_decl.name {
 304                 Some(name) => if name.as_str().starts_with("_") {
 305                     continue;
 306                 },
 307                 None => continue,
 308             }
 309
 310             let span = local_decl.source_info.span;
 311             if span.compiler_desugaring_kind().is_some() {
 312                 // If the `mut` arises as part of a desugaring, we should ignore it.
 313                 continue;
 314             }
 315
 316             let mut_span = tcx.sess.source_map().span_until_non_whitespace(span);
 317             tcx.struct_span_lint_node(
 318                 UNUSED_MUT,
 319                 vsi[local_decl.source_info.scope].lint_root,
 320                 span,
 321                 "variable does not need to be mutable",
 322             )
 323             .span_suggestion_short_with_applicability(
 324                 mut_span,
 325                 "remove this `mut`",
 326                 String::new(),
 327                 Applicability::MachineApplicable,
 328             )
 329             .emit();
 330         }
 331     }
 332
 333     // Buffer any move errors that we collected and de-duplicated.
 334     for (_, (_, diag)) in mbcx.move_error_reported {
 335         diag.buffer(&mut mbcx.errors_buffer);
 336     }
 337
 338     if !mbcx.errors_buffer.is_empty() {
 339         mbcx.errors_buffer.sort_by_key(|diag| diag.span.primary_span());
 340
 341         if tcx.migrate_borrowck() {
 342             // When borrowck=migrate, check if AST-borrowck would
 343             // error on the given code.
 344
 345             // rust-lang/rust#55492: loop over parents to ensure that
 346             // errors that AST-borrowck only detects in some parent of
 347             // a closure still allows NLL to signal an error.
 348             let mut curr_def_id = def_id;
 349             let signalled_any_error = loop {
 350                 match tcx.borrowck(curr_def_id).signalled_any_error {
 351                     SignalledError::NoErrorsSeen => {
 352                         // keep traversing (and borrow-checking) parents
 353                     }
 354                     SignalledError::SawSomeError => {
 355                         // stop search here
 356                         break SignalledError::SawSomeError;
 357                     }
 358                 }
 359
 360                 if tcx.is_closure(curr_def_id) {
 361                     curr_def_id = tcx.parent_def_id(curr_def_id)
 362                         .expect("a closure must have a parent_def_id");
 363                 } else {
 364                     break SignalledError::NoErrorsSeen;
 365                 }
 366             };
 367
 368             match signalled_any_error {
 369                 SignalledError::NoErrorsSeen => {
 370                     // if AST-borrowck signalled no errors, then
 371                     // downgrade all the buffered MIR-borrowck errors
 372                     // to warnings.
 373                     for err in &mut mbcx.errors_buffer {
 374                         if err.is_error() {
 375                             err.level = Level::Warning;
 376                             err.warn("This error has been downgraded to a warning \
 377                                       for backwards compatibility with previous releases.\n\
 378                                       It represents potential unsoundness in your code.\n\
 379                                       This warning will become a hard error in the future.");
 380                         }
 381                     }
 382                 }
 383                 SignalledError::SawSomeError => {
 384                     // if AST-borrowck signalled a (cancelled) error,
 385                     // then we will just emit the buffered
 386                     // MIR-borrowck errors as normal.
 387                 }
 388             }
 389         }
 390
 391         for diag in mbcx.errors_buffer.drain(..) {
 392             DiagnosticBuilder::new_diagnostic(mbcx.infcx.tcx.sess.diagnostic(), diag).emit();
 393         }
 394     }
 395
 396     let result = BorrowCheckResult {
 397         closure_requirements: opt_closure_req,
 398         used_mut_upvars: mbcx.used_mut_upvars,
 399     };
 400
 401     debug!("do_mir_borrowck: result = {:#?}", result);
 402
 403     result
 404 }
 405
 406 pub struct MirBorrowckCtxt<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
 407     infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
 408     mir: &'cx Mir<'tcx>,
 409     mir_def_id: DefId,
 410     move_data: &'cx MoveData<'tcx>,
 411
 412     /// Map from MIR `Location` to `LocationIndex`; created
 413     /// when MIR borrowck begins.
 414     location_table: &'cx LocationTable,
 415
 416     movable_generator: bool,
 417     /// This keeps track of whether local variables are free-ed when the function
 418     /// exits even without a `StorageDead`, which appears to be the case for
 419     /// constants.
 420     ///
 421     /// I'm not sure this is the right approach - @eddyb could you try and
 422     /// figure this out?
 423     locals_are_invalidated_at_exit: bool,
 424     /// This field keeps track of when borrow errors are reported in the access_place function
 425     /// so that there is no duplicate reporting. This field cannot also be used for the conflicting
 426     /// borrow errors that is handled by the `reservation_error_reported` field as the inclusion
 427     /// of the `Span` type (while required to mute some errors) stops the muting of the reservation
 428     /// errors.
 429     access_place_error_reported: FxHashSet<(Place<'tcx>, Span)>,
 430     /// This field keeps track of when borrow conflict errors are reported
 431     /// for reservations, so that we don't report seemingly duplicate
 432     /// errors for corresponding activations
 433     ///
 434     /// FIXME: Ideally this would be a set of BorrowIndex, not Places,
 435     /// but it is currently inconvenient to track down the BorrowIndex
 436     /// at the time we detect and report a reservation error.
 437     reservation_error_reported: FxHashSet<Place<'tcx>>,
 438     /// This field keeps track of move errors that are to be reported for given move indicies.
 439     ///
 440     /// There are situations where many errors can be reported for a single move out (see #53807)
 441     /// and we want only the best of those errors.
 442     ///
 443     /// The `report_use_of_moved_or_uninitialized` function checks this map and replaces the
 444     /// diagnostic (if there is one) if the `Place` of the error being reported is a prefix of the
 445     /// `Place` of the previous most diagnostic. This happens instead of buffering the error. Once
 446     /// all move errors have been reported, any diagnostics in this map are added to the buffer
 447     /// to be emitted.
 448     ///
 449     /// `BTreeMap` is used to preserve the order of insertions when iterating. This is necessary
 450     /// when errors in the map are being re-added to the error buffer so that errors with the
 451     /// same primary span come out in a consistent order.
 452     move_error_reported: BTreeMap<Vec<MoveOutIndex>, (Place<'tcx>, DiagnosticBuilder<'cx>)>,
 453     /// This field keeps track of errors reported in the checking of uninitialized variables,
 454     /// so that we don't report seemingly duplicate errors.
 455     uninitialized_error_reported: FxHashSet<Place<'tcx>>,
 456     /// Errors to be reported buffer
 457     errors_buffer: Vec<Diagnostic>,
 458     /// This field keeps track of all the local variables that are declared mut and are mutated.
 459     /// Used for the warning issued by an unused mutable local variable.
 460     used_mut: FxHashSet<Local>,
 461     /// If the function we're checking is a closure, then we'll need to report back the list of
 462     /// mutable upvars that have been used. This field keeps track of them.
 463     used_mut_upvars: SmallVec<[Field; 8]>,
 464     /// Non-lexical region inference context, if NLL is enabled.  This
 465     /// contains the results from region inference and lets us e.g.
 466     /// find out which CFG points are contained in each borrow region.
 467     nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
 468
 469     /// The set of borrows extracted from the MIR
 470     borrow_set: Rc<BorrowSet<'tcx>>,
 471
 472     /// Dominators for MIR
 473     dominators: Dominators<BasicBlock>,
 474 }
 475
 476 // Check that:
 477 // 1. assignments are always made to mutable locations (FIXME: does that still really go here?)
 478 // 2. loans made in overlapping scopes do not conflict
 479 // 3. assignments do not affect things loaned out as immutable
 480 // 4. moves do not affect things loaned out in any way
 481 impl<'cx, 'gcx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
 482     type FlowState = Flows<'cx, 'gcx, 'tcx>;
 483
 484     fn mir(&self) -> &'cx Mir<'tcx> {
 485         self.mir
 486     }
 487
 488     fn visit_block_entry(&mut self, bb: BasicBlock, flow_state: &Self::FlowState) {
 489         debug!("MirBorrowckCtxt::process_block({:?}): {}", bb, flow_state);
 490     }
 491
 492     fn visit_statement_entry(
 493         &mut self,
 494         location: Location,
 495         stmt: &Statement<'tcx>,
 496         flow_state: &Self::FlowState,
 497     ) {
 498         debug!(
 499             "MirBorrowckCtxt::process_statement({:?}, {:?}): {}",
 500             location, stmt, flow_state
 501         );
 502         let span = stmt.source_info.span;
 503
 504         self.check_activations(location, span, flow_state);
 505
 506         match stmt.kind {
 507             StatementKind::Assign(ref lhs, ref rhs) => {
 508                 self.consume_rvalue(
 509                     ContextKind::AssignRhs.new(location),
 510                     (rhs, span),
 511                     location,
 512                     flow_state,
 513                 );
 514
 515                 self.mutate_place(
 516                     ContextKind::AssignLhs.new(location),
 517                     (lhs, span),
 518                     Shallow(None),
 519                     JustWrite,
 520                     flow_state,
 521                 );
 522             }
 523             StatementKind::FakeRead(_, ref place) => {
 524                 // Read for match doesn't access any memory and is used to
 525                 // assert that a place is safe and live. So we don't have to
 526                 // do any checks here.
 527                 //
 528                 // FIXME: Remove check that the place is initialized. This is
 529                 // needed for now because matches don't have never patterns yet.
 530                 // So this is the only place we prevent
 531                 //      let x: !;
 532                 //      match x {};
 533                 // from compiling.
 534                 self.check_if_path_or_subpath_is_moved(
 535                     ContextKind::FakeRead.new(location),
 536                     InitializationRequiringAction::Use,
 537                     (place, span),
 538                     flow_state,
 539                 );
 540             }
 541             StatementKind::SetDiscriminant {
 542                 ref place,
 543                 variant_index: _,
 544             } => {
 545                 self.mutate_place(
 546                     ContextKind::SetDiscrim.new(location),
 547                     (place, span),
 548                     Shallow(Some(ArtificialField::Discriminant)),
 549                     JustWrite,
 550                     flow_state,
 551                 );
 552             }
 553             StatementKind::InlineAsm {
 554                 ref asm,
 555                 ref outputs,
 556                 ref inputs,
 557             } => {
 558                 let context = ContextKind::InlineAsm.new(location);
 559                 for (o, output) in asm.outputs.iter().zip(outputs.iter()) {
 560                     if o.is_indirect {
 561                         // FIXME(eddyb) indirect inline asm outputs should
 562                         // be encoeded through MIR place derefs instead.
 563                         self.access_place(
 564                             context,
 565                             (output, o.span),
 566                             (Deep, Read(ReadKind::Copy)),
 567                             LocalMutationIsAllowed::No,
 568                             flow_state,
 569                         );
 570                         self.check_if_path_or_subpath_is_moved(
 571                             context,
 572                             InitializationRequiringAction::Use,
 573                             (output, o.span),
 574                             flow_state,
 575                         );
 576                     } else {
 577                         self.mutate_place(
 578                             context,
 579                             (output, o.span),
 580                             if o.is_rw { Deep } else { Shallow(None) },
 581                             if o.is_rw { WriteAndRead } else { JustWrite },
 582                             flow_state,
 583                         );
 584                     }
 585                 }
 586                 for (_, input) in inputs.iter() {
 587                     self.consume_operand(context, (input, span), flow_state);
 588                 }
 589             }
 590             StatementKind::Nop
 591             | StatementKind::AscribeUserType(..)
 592             | StatementKind::Retag { .. }
 593             | StatementKind::EscapeToRaw { .. }
 594             | StatementKind::StorageLive(..) => {
 595                 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
 596                 // to borrow check.
 597             }
 598             StatementKind::StorageDead(local) => {
 599                 self.access_place(
 600                     ContextKind::StorageDead.new(location),
 601                     (&Place::Local(local), span),
 602                     (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
 603                     LocalMutationIsAllowed::Yes,
 604                     flow_state,
 605                 );
 606             }
 607         }
 608     }
 609
 610     fn visit_terminator_entry(
 611         &mut self,
 612         location: Location,
 613         term: &Terminator<'tcx>,
 614         flow_state: &Self::FlowState,
 615     ) {
 616         let loc = location;
 617         debug!(
 618             "MirBorrowckCtxt::process_terminator({:?}, {:?}): {}",
 619             location, term, flow_state
 620         );
 621         let span = term.source_info.span;
 622
 623         self.check_activations(location, span, flow_state);
 624
 625         match term.kind {
 626             TerminatorKind::SwitchInt {
 627                 ref discr,
 628                 switch_ty: _,
 629                 values: _,
 630                 targets: _,
 631             } => {
 632                 self.consume_operand(ContextKind::SwitchInt.new(loc), (discr, span), flow_state);
 633             }
 634             TerminatorKind::Drop {
 635                 location: ref drop_place,
 636                 target: _,
 637                 unwind: _,
 638             } => {
 639                 let gcx = self.infcx.tcx.global_tcx();
 640
 641                 // Compute the type with accurate region information.
 642                 let drop_place_ty = drop_place.ty(self.mir, self.infcx.tcx);
 643
 644                 // Erase the regions.
 645                 let drop_place_ty = self.infcx.tcx.erase_regions(&drop_place_ty)
 646                     .to_ty(self.infcx.tcx);
 647
 648                 // "Lift" into the gcx -- once regions are erased, this type should be in the
 649                 // global arenas; this "lift" operation basically just asserts that is true, but
 650                 // that is useful later.
 651                 let drop_place_ty = gcx.lift(&drop_place_ty).unwrap();
 652
 653                 debug!("visit_terminator_drop \
 654                         loc: {:?} term: {:?} drop_place: {:?} drop_place_ty: {:?} span: {:?}",
 655                        loc, term, drop_place, drop_place_ty, span);
 656
 657                 self.access_place(
 658                     ContextKind::Drop.new(loc),
 659                     (drop_place, span),
 660                     (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
 661                     LocalMutationIsAllowed::Yes,
 662                     flow_state,
 663                 );
 664             }
 665             TerminatorKind::DropAndReplace {
 666                 location: ref drop_place,
 667                 value: ref new_value,
 668                 target: _,
 669                 unwind: _,
 670             } => {
 671                 self.mutate_place(
 672                     ContextKind::DropAndReplace.new(loc),
 673                     (drop_place, span),
 674                     Deep,
 675                     JustWrite,
 676                     flow_state,
 677                 );
 678                 self.consume_operand(
 679                     ContextKind::DropAndReplace.new(loc),
 680                     (new_value, span),
 681                     flow_state,
 682                 );
 683             }
 684             TerminatorKind::Call {
 685                 ref func,
 686                 ref args,
 687                 ref destination,
 688                 cleanup: _,
 689                 from_hir_call: _,
 690             } => {
 691                 self.consume_operand(ContextKind::CallOperator.new(loc), (func, span), flow_state);
 692                 for arg in args {
 693                     self.consume_operand(
 694                         ContextKind::CallOperand.new(loc),
 695                         (arg, span),
 696                         flow_state,
 697                     );
 698                 }
 699                 if let Some((ref dest, _ /*bb*/)) = *destination {
 700                     self.mutate_place(
 701                         ContextKind::CallDest.new(loc),
 702                         (dest, span),
 703                         Deep,
 704                         JustWrite,
 705                         flow_state,
 706                     );
 707                 }
 708             }
 709             TerminatorKind::Assert {
 710                 ref cond,
 711                 expected: _,
 712                 ref msg,
 713                 target: _,
 714                 cleanup: _,
 715             } => {
 716                 self.consume_operand(ContextKind::Assert.new(loc), (cond, span), flow_state);
 717                 use rustc::mir::interpret::EvalErrorKind::BoundsCheck;
 718                 if let BoundsCheck { ref len, ref index } = *msg {
 719                     self.consume_operand(ContextKind::Assert.new(loc), (len, span), flow_state);
 720                     self.consume_operand(ContextKind::Assert.new(loc), (index, span), flow_state);
 721                 }
 722             }
 723
 724             TerminatorKind::Yield {
 725                 ref value,
 726                 resume: _,
 727                 drop: _,
 728             } => {
 729                 self.consume_operand(ContextKind::Yield.new(loc), (value, span), flow_state);
 730
 731                 if self.movable_generator {
 732                     // Look for any active borrows to locals
 733                     let borrow_set = self.borrow_set.clone();
 734                     flow_state.with_outgoing_borrows(|borrows| {
 735                         for i in borrows {
 736                             let borrow = &borrow_set[i];
 737                             self.check_for_local_borrow(borrow, span);
 738                         }
 739                     });
 740                 }
 741             }
 742
 743             TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
 744                 // Returning from the function implicitly kills storage for all locals and statics.
 745                 // Often, the storage will already have been killed by an explicit
 746                 // StorageDead, but we don't always emit those (notably on unwind paths),
 747                 // so this "extra check" serves as a kind of backup.
 748                 let borrow_set = self.borrow_set.clone();
 749                 flow_state.with_outgoing_borrows(|borrows| {
 750                     for i in borrows {
 751                         let borrow = &borrow_set[i];
 752                         let context = ContextKind::StorageDead.new(loc);
 753                         self.check_for_invalidation_at_exit(context, borrow, span);
 754                     }
 755                 });
 756             }
 757             TerminatorKind::Goto { target: _ }
 758             | TerminatorKind::Abort
 759             | TerminatorKind::Unreachable
 760             | TerminatorKind::FalseEdges {
 761                 real_target: _,
 762                 imaginary_targets: _,
 763             }
 764             | TerminatorKind::FalseUnwind {
 765                 real_target: _,
 766                 unwind: _,
 767             } => {
 768                 // no data used, thus irrelevant to borrowck
 769             }
 770         }
 771     }
 772 }
 773
 774 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 775 enum MutateMode {
 776     JustWrite,
 777     WriteAndRead,
 778 }
 779
 780 use self::ReadOrWrite::{Activation, Read, Reservation, Write};
 781 use self::AccessDepth::{Deep, Shallow};
 782
 783 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 784 enum ArtificialField {
 785     Discriminant,
 786     ArrayLength,
 787     ShallowBorrow,
 788 }
 789
 790 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 791 enum AccessDepth {
 792     /// From the RFC: "A *shallow* access means that the immediate
 793     /// fields reached at P are accessed, but references or pointers
 794     /// found within are not dereferenced. Right now, the only access
 795     /// that is shallow is an assignment like `x = ...;`, which would
 796     /// be a *shallow write* of `x`."
 797     Shallow(Option<ArtificialField>),
 798
 799     /// From the RFC: "A *deep* access means that all data reachable
 800     /// through the given place may be invalidated or accesses by
 801     /// this action."
 802     Deep,
 803
 804     /// Access is Deep only when there is a Drop implementation that
 805     /// can reach the data behind the reference.
 806     Drop,
 807 }
 808
 809 /// Kind of access to a value: read or write
 810 /// (For informational purposes only)
 811 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 812 enum ReadOrWrite {
 813     /// From the RFC: "A *read* means that the existing data may be
 814     /// read, but will not be changed."
 815     Read(ReadKind),
 816
 817     /// From the RFC: "A *write* means that the data may be mutated to
 818     /// new values or otherwise invalidated (for example, it could be
 819     /// de-initialized, as in a move operation).
 820     Write(WriteKind),
 821
 822     /// For two-phase borrows, we distinguish a reservation (which is treated
 823     /// like a Read) from an activation (which is treated like a write), and
 824     /// each of those is furthermore distinguished from Reads/Writes above.
 825     Reservation(WriteKind),
 826     Activation(WriteKind, BorrowIndex),
 827 }
 828
 829 /// Kind of read access to a value
 830 /// (For informational purposes only)
 831 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 832 enum ReadKind {
 833     Borrow(BorrowKind),
 834     Copy,
 835 }
 836
 837 /// Kind of write access to a value
 838 /// (For informational purposes only)
 839 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 840 enum WriteKind {
 841     StorageDeadOrDrop,
 842     MutableBorrow(BorrowKind),
 843     Mutate,
 844     Move,
 845 }
 846
 847 /// When checking permissions for a place access, this flag is used to indicate that an immutable
 848 /// local place can be mutated.
 849 ///
 850 /// FIXME: @nikomatsakis suggested that this flag could be removed with the following modifications:
 851 /// - Merge `check_access_permissions()` and `check_if_reassignment_to_immutable_state()`
 852 /// - Split `is_mutable()` into `is_assignable()` (can be directly assigned) and
 853 ///   `is_declared_mutable()`
 854 /// - Take flow state into consideration in `is_assignable()` for local variables
 855 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 856 enum LocalMutationIsAllowed {
 857     Yes,
 858     /// We want use of immutable upvars to cause a "write to immutable upvar"
 859     /// error, not an "reassignment" error.
 860     ExceptUpvars,
 861     No,
 862 }
 863
 864 #[derive(Copy, Clone, Debug)]
 865 enum InitializationRequiringAction {
 866     Update,
 867     Borrow,
 868     MatchOn,
 869     Use,
 870     Assignment,
 871     PartialAssignment,
 872 }
 873
 874 struct RootPlace<'d, 'tcx: 'd> {
 875     place: &'d Place<'tcx>,
 876     is_local_mutation_allowed: LocalMutationIsAllowed,
 877 }
 878
 879 impl InitializationRequiringAction {
 880     fn as_noun(self) -> &'static str {
 881         match self {
 882             InitializationRequiringAction::Update => "update",
 883             InitializationRequiringAction::Borrow => "borrow",
 884             InitializationRequiringAction::MatchOn => "use", // no good noun
 885             InitializationRequiringAction::Use => "use",
 886             InitializationRequiringAction::Assignment => "assign",
 887             InitializationRequiringAction::PartialAssignment => "assign to part",
 888         }
 889     }
 890
 891     fn as_verb_in_past_tense(self) -> &'static str {
 892         match self {
 893             InitializationRequiringAction::Update => "updated",
 894             InitializationRequiringAction::Borrow => "borrowed",
 895             InitializationRequiringAction::MatchOn => "matched on",
 896             InitializationRequiringAction::Use => "used",
 897             InitializationRequiringAction::Assignment => "assigned",
 898             InitializationRequiringAction::PartialAssignment => "partially assigned",
 899         }
 900     }
 901 }
 902
 903 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
 904     /// Checks an access to the given place to see if it is allowed. Examines the set of borrows
 905     /// that are in scope, as well as which paths have been initialized, to ensure that (a) the
 906     /// place is initialized and (b) it is not borrowed in some way that would prevent this
 907     /// access.
 908     ///
 909     /// Returns true if an error is reported, false otherwise.
 910     fn access_place(
 911         &mut self,
 912         context: Context,
 913         place_span: (&Place<'tcx>, Span),
 914         kind: (AccessDepth, ReadOrWrite),
 915         is_local_mutation_allowed: LocalMutationIsAllowed,
 916         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 917     ) {
 918         let (sd, rw) = kind;
 919
 920         if let Activation(_, borrow_index) = rw {
 921             if self.reservation_error_reported.contains(&place_span.0) {
 922                 debug!(
 923                     "skipping access_place for activation of invalid reservation \
 924                      place: {:?} borrow_index: {:?}",
 925                     place_span.0, borrow_index
 926                 );
 927                 return;
 928             }
 929         }
 930
 931         // Check is_empty() first because it's the common case, and doing that
 932         // way we avoid the clone() call.
 933         if !self.access_place_error_reported.is_empty() &&
 934            self
 935             .access_place_error_reported
 936             .contains(&(place_span.0.clone(), place_span.1))
 937         {
 938             debug!(
 939                 "access_place: suppressing error place_span=`{:?}` kind=`{:?}`",
 940                 place_span, kind
 941             );
 942             return;
 943         }
 944
 945         let mutability_error =
 946             self.check_access_permissions(
 947                 place_span,
 948                 rw,
 949                 is_local_mutation_allowed,
 950                 flow_state,
 951                 context.loc,
 952             );
 953         let conflict_error =
 954             self.check_access_for_conflict(context, place_span, sd, rw, flow_state);
 955
 956         if conflict_error || mutability_error {
 957             debug!(
 958                 "access_place: logging error place_span=`{:?}` kind=`{:?}`",
 959                 place_span, kind
 960             );
 961             self.access_place_error_reported
 962                 .insert((place_span.0.clone(), place_span.1));
 963         }
 964     }
 965
 966     fn check_access_for_conflict(
 967         &mut self,
 968         context: Context,
 969         place_span: (&Place<'tcx>, Span),
 970         sd: AccessDepth,
 971         rw: ReadOrWrite,
 972         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 973     ) -> bool {
 974         debug!(
 975             "check_access_for_conflict(context={:?}, place_span={:?}, sd={:?}, rw={:?})",
 976             context, place_span, sd, rw,
 977         );
 978
 979         let mut error_reported = false;
 980         let tcx = self.infcx.tcx;
 981         let mir = self.mir;
 982         let location = self.location_table.start_index(context.loc);
 983         let borrow_set = self.borrow_set.clone();
 984         each_borrow_involving_path(
 985             self,
 986             tcx,
 987             mir,
 988             context,
 989             (sd, place_span.0),
 990             &borrow_set,
 991             flow_state.borrows_in_scope(location),
 992             |this, borrow_index, borrow| match (rw, borrow.kind) {
 993                 // Obviously an activation is compatible with its own
 994                 // reservation (or even prior activating uses of same
 995                 // borrow); so don't check if they interfere.
 996                 //
 997                 // NOTE: *reservations* do conflict with themselves;
 998                 // thus aren't injecting unsoundenss w/ this check.)
 999                 (Activation(_, activating), _) if activating == borrow_index => {
1000                     debug!(
1001                         "check_access_for_conflict place_span: {:?} sd: {:?} rw: {:?} \
1002                          skipping {:?} b/c activation of same borrow_index",
1003                         place_span,
1004                         sd,
1005                         rw,
1006                         (borrow_index, borrow),
1007                     );
1008                     Control::Continue
1009                 }
1010
1011                 (Read(_), BorrowKind::Shared) | (Reservation(..), BorrowKind::Shared)
1012                 | (Read(_), BorrowKind::Shallow) | (Reservation(..), BorrowKind::Shallow) => {
1013                     Control::Continue
1014                 }
1015
1016                 (Write(WriteKind::Move), BorrowKind::Shallow) => {
1017                     // Handled by initialization checks.
1018                     Control::Continue
1019                 }
1020
1021                 (Read(kind), BorrowKind::Unique) | (Read(kind), BorrowKind::Mut { .. }) => {
1022                     // Reading from mere reservations of mutable-borrows is OK.
1023                     if !is_active(&this.dominators, borrow, context.loc) {
1024                         assert!(allow_two_phase_borrow(&this.infcx.tcx, borrow.kind));
1025                         return Control::Continue;
1026                     }
1027
1028                     error_reported = true;
1029                     match kind {
1030                         ReadKind::Copy  => {
1031                             this.report_use_while_mutably_borrowed(context, place_span, borrow)
1032                         }
1033                         ReadKind::Borrow(bk) => {
1034                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1035                         }
1036                     }
1037                     Control::Break
1038                 }
1039
1040                 (Reservation(kind), BorrowKind::Unique)
1041                 | (Reservation(kind), BorrowKind::Mut { .. })
1042                 | (Activation(kind, _), _)
1043                 | (Write(kind), _) => {
1044                     match rw {
1045                         Reservation(_) => {
1046                             debug!(
1047                                 "recording invalid reservation of \
1048                                  place: {:?}",
1049                                 place_span.0
1050                             );
1051                             this.reservation_error_reported.insert(place_span.0.clone());
1052                         }
1053                         Activation(_, activating) => {
1054                             debug!(
1055                                 "observing check_place for activation of \
1056                                  borrow_index: {:?}",
1057                                 activating
1058                             );
1059                         }
1060                         Read(..) | Write(..) => {}
1061                     }
1062
1063                     error_reported = true;
1064                     match kind {
1065                         WriteKind::MutableBorrow(bk) => {
1066                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1067                         }
1068                         WriteKind::StorageDeadOrDrop => {
1069                             this.report_borrowed_value_does_not_live_long_enough(
1070                                 context,
1071                                 borrow,
1072                                 place_span,
1073                                 Some(kind))
1074                         }
1075                         WriteKind::Mutate => {
1076                             this.report_illegal_mutation_of_borrowed(context, place_span, borrow)
1077                         }
1078                         WriteKind::Move => {
1079                             this.report_move_out_while_borrowed(context, place_span, &borrow)
1080                         }
1081                     }
1082                     Control::Break
1083                 }
1084             },
1085         );
1086
1087         error_reported
1088     }
1089
1090     fn mutate_place(
1091         &mut self,
1092         context: Context,
1093         place_span: (&Place<'tcx>, Span),
1094         kind: AccessDepth,
1095         mode: MutateMode,
1096         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1097     ) {
1098         // Write of P[i] or *P, or WriteAndRead of any P, requires P init'd.
1099         match mode {
1100             MutateMode::WriteAndRead => {
1101                 self.check_if_path_or_subpath_is_moved(
1102                     context,
1103                     InitializationRequiringAction::Update,
1104                     place_span,
1105                     flow_state,
1106                 );
1107             }
1108             MutateMode::JustWrite => {
1109                 self.check_if_assigned_path_is_moved(context, place_span, flow_state);
1110             }
1111         }
1112
1113         // Special case: you can assign a immutable local variable
1114         // (e.g., `x = ...`) so long as it has never been initialized
1115         // before (at this point in the flow).
1116         if let &Place::Local(local) = place_span.0 {
1117             if let Mutability::Not = self.mir.local_decls[local].mutability {
1118                 // check for reassignments to immutable local variables
1119                 self.check_if_reassignment_to_immutable_state(
1120                     context,
1121                     local,
1122                     place_span,
1123                     flow_state,
1124                 );
1125                 return;
1126             }
1127         }
1128
1129         // Otherwise, use the normal access permission rules.
1130         self.access_place(
1131             context,
1132             place_span,
1133             (kind, Write(WriteKind::Mutate)),
1134             LocalMutationIsAllowed::No,
1135             flow_state,
1136         );
1137     }
1138
1139     fn consume_rvalue(
1140         &mut self,
1141         context: Context,
1142         (rvalue, span): (&Rvalue<'tcx>, Span),
1143         _location: Location,
1144         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1145     ) {
1146         match *rvalue {
1147             Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
1148                 let access_kind = match bk {
1149                     BorrowKind::Shallow => {
1150                         (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
1151                     },
1152                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
1153                     BorrowKind::Unique | BorrowKind::Mut { .. } => {
1154                         let wk = WriteKind::MutableBorrow(bk);
1155                         if allow_two_phase_borrow(&self.infcx.tcx, bk) {
1156                             (Deep, Reservation(wk))
1157                         } else {
1158                             (Deep, Write(wk))
1159                         }
1160                     }
1161                 };
1162
1163                 self.access_place(
1164                     context,
1165                     (place, span),
1166                     access_kind,
1167                     LocalMutationIsAllowed::No,
1168                     flow_state,
1169                 );
1170
1171                 let action = if bk == BorrowKind::Shallow {
1172                     InitializationRequiringAction::MatchOn
1173                 } else {
1174                     InitializationRequiringAction::Borrow
1175                 };
1176
1177                 self.check_if_path_or_subpath_is_moved(
1178                     context,
1179                     action,
1180                     (place, span),
1181                     flow_state,
1182                 );
1183             }
1184
1185             Rvalue::Use(ref operand)
1186             | Rvalue::Repeat(ref operand, _)
1187             | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
1188             | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
1189                 self.consume_operand(context, (operand, span), flow_state)
1190             }
1191
1192             Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
1193                 let af = match *rvalue {
1194                     Rvalue::Len(..) => ArtificialField::ArrayLength,
1195                     Rvalue::Discriminant(..) => ArtificialField::Discriminant,
1196                     _ => unreachable!(),
1197                 };
1198                 self.access_place(
1199                     context,
1200                     (place, span),
1201                     (Shallow(Some(af)), Read(ReadKind::Copy)),
1202                     LocalMutationIsAllowed::No,
1203                     flow_state,
1204                 );
1205                 self.check_if_path_or_subpath_is_moved(
1206                     context,
1207                     InitializationRequiringAction::Use,
1208                     (place, span),
1209                     flow_state,
1210                 );
1211             }
1212
1213             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
1214             | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
1215                 self.consume_operand(context, (operand1, span), flow_state);
1216                 self.consume_operand(context, (operand2, span), flow_state);
1217             }
1218
1219             Rvalue::NullaryOp(_op, _ty) => {
1220                 // nullary ops take no dynamic input; no borrowck effect.
1221                 //
1222                 // FIXME: is above actually true? Do we want to track
1223                 // the fact that uninitialized data can be created via
1224                 // `NullOp::Box`?
1225             }
1226
1227             Rvalue::Aggregate(ref aggregate_kind, ref operands) => {
1228                 // We need to report back the list of mutable upvars that were
1229                 // moved into the closure and subsequently used by the closure,
1230                 // in order to populate our used_mut set.
1231                 match **aggregate_kind {
1232                     AggregateKind::Closure(def_id, _)
1233                     | AggregateKind::Generator(def_id, _, _) => {
1234                         let BorrowCheckResult {
1235                             used_mut_upvars, ..
1236                         } = self.infcx.tcx.mir_borrowck(def_id);
1237                         debug!("{:?} used_mut_upvars={:?}", def_id, used_mut_upvars);
1238                         for field in used_mut_upvars {
1239                             // This relies on the current way that by-value
1240                             // captures of a closure are copied/moved directly
1241                             // when generating MIR.
1242                             match operands[field.index()] {
1243                                 Operand::Move(Place::Local(local))
1244                                 | Operand::Copy(Place::Local(local)) => {
1245                                     self.used_mut.insert(local);
1246                                 }
1247                                 Operand::Move(ref place @ Place::Projection(_))
1248                                 | Operand::Copy(ref place @ Place::Projection(_)) => {
1249                                     if let Some(field) = place.is_upvar_field_projection(
1250                                             self.mir, &self.infcx.tcx) {
1251                                         self.used_mut_upvars.push(field);
1252                                     }
1253                                 }
1254                                 Operand::Move(Place::Static(..))
1255                                 | Operand::Copy(Place::Static(..))
1256                                 | Operand::Move(Place::Promoted(..))
1257                                 | Operand::Copy(Place::Promoted(..))
1258                                 | Operand::Constant(..) => {}
1259                             }
1260                         }
1261                     }
1262                     AggregateKind::Adt(..)
1263                     | AggregateKind::Array(..)
1264                     | AggregateKind::Tuple { .. } => (),
1265                 }
1266
1267                 for operand in operands {
1268                     self.consume_operand(context, (operand, span), flow_state);
1269                 }
1270             }
1271         }
1272     }
1273
1274     fn consume_operand(
1275         &mut self,
1276         context: Context,
1277         (operand, span): (&Operand<'tcx>, Span),
1278         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1279     ) {
1280         match *operand {
1281             Operand::Copy(ref place) => {
1282                 // copy of place: check if this is "copy of frozen path"
1283                 // (FIXME: see check_loans.rs)
1284                 self.access_place(
1285                     context,
1286                     (place, span),
1287                     (Deep, Read(ReadKind::Copy)),
1288                     LocalMutationIsAllowed::No,
1289                     flow_state,
1290                 );
1291
1292                 // Finally, check if path was already moved.
1293                 self.check_if_path_or_subpath_is_moved(
1294                     context,
1295                     InitializationRequiringAction::Use,
1296                     (place, span),
1297                     flow_state,
1298                 );
1299             }
1300             Operand::Move(ref place) => {
1301                 // move of place: check if this is move of already borrowed path
1302                 self.access_place(
1303                     context,
1304                     (place, span),
1305                     (Deep, Write(WriteKind::Move)),
1306                     LocalMutationIsAllowed::Yes,
1307                     flow_state,
1308                 );
1309
1310                 // Finally, check if path was already moved.
1311                 self.check_if_path_or_subpath_is_moved(
1312                     context,
1313                     InitializationRequiringAction::Use,
1314                     (place, span),
1315                     flow_state,
1316                 );
1317             }
1318             Operand::Constant(_) => {}
1319         }
1320     }
1321
1322     /// Checks whether a borrow of this place is invalidated when the function
1323     /// exits
1324     fn check_for_invalidation_at_exit(
1325         &mut self,
1326         context: Context,
1327         borrow: &BorrowData<'tcx>,
1328         span: Span,
1329     ) {
1330         debug!("check_for_invalidation_at_exit({:?})", borrow);
1331         let place = &borrow.borrowed_place;
1332         let root_place = self.prefixes(place, PrefixSet::All).last().unwrap();
1333
1334         // FIXME(nll-rfc#40): do more precise destructor tracking here. For now
1335         // we just know that all locals are dropped at function exit (otherwise
1336         // we'll have a memory leak) and assume that all statics have a destructor.
1337         //
1338         // FIXME: allow thread-locals to borrow other thread locals?
1339         let (might_be_alive, will_be_dropped) = match root_place {
1340             Place::Promoted(_) => (true, false),
1341             Place::Static(_) => {
1342                 // Thread-locals might be dropped after the function exits, but
1343                 // "true" statics will never be.
1344                 let is_thread_local = self.is_place_thread_local(&root_place);
1345                 (true, is_thread_local)
1346             }
1347             Place::Local(_) => {
1348                 // Locals are always dropped at function exit, and if they
1349                 // have a destructor it would've been called already.
1350                 (false, self.locals_are_invalidated_at_exit)
1351             }
1352             Place::Projection(..) => {
1353                 bug!("root of {:?} is a projection ({:?})?", place, root_place)
1354             }
1355         };
1356
1357         if !will_be_dropped {
1358             debug!(
1359                 "place_is_invalidated_at_exit({:?}) - won't be dropped",
1360                 place
1361             );
1362             return;
1363         }
1364
1365         let sd = if might_be_alive { Deep } else { Shallow(None) };
1366
1367         if places_conflict::borrow_conflicts_with_place(
1368             self.infcx.tcx,
1369             self.mir,
1370             place,
1371             borrow.kind,
1372             root_place,
1373             sd
1374         ) {
1375             debug!("check_for_invalidation_at_exit({:?}): INVALID", place);
1376             // FIXME: should be talking about the region lifetime instead
1377             // of just a span here.
1378             let span = self.infcx.tcx.sess.source_map().end_point(span);
1379             self.report_borrowed_value_does_not_live_long_enough(
1380                 context,
1381                 borrow,
1382                 (place, span),
1383                 None,
1384             )
1385         }
1386     }
1387
1388     /// Reports an error if this is a borrow of local data.
1389     /// This is called for all Yield statements on movable generators
1390     fn check_for_local_borrow(&mut self, borrow: &BorrowData<'tcx>, yield_span: Span) {
1391         debug!("check_for_local_borrow({:?})", borrow);
1392
1393         if borrow_of_local_data(&borrow.borrowed_place) {
1394             let err = self.infcx.tcx
1395                 .cannot_borrow_across_generator_yield(
1396                     self.retrieve_borrow_spans(borrow).var_or_use(),
1397                     yield_span,
1398                     Origin::Mir,
1399                 );
1400
1401             err.buffer(&mut self.errors_buffer);
1402         }
1403     }
1404
1405     fn check_activations(
1406         &mut self,
1407         location: Location,
1408         span: Span,
1409         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1410     ) {
1411         if !self.infcx.tcx.two_phase_borrows() {
1412             return;
1413         }
1414
1415         // Two-phase borrow support: For each activation that is newly
1416         // generated at this statement, check if it interferes with
1417         // another borrow.
1418         let borrow_set = self.borrow_set.clone();
1419         for &borrow_index in borrow_set.activations_at_location(location) {
1420             let borrow = &borrow_set[borrow_index];
1421
1422             // only mutable borrows should be 2-phase
1423             assert!(match borrow.kind {
1424                 BorrowKind::Shared | BorrowKind::Shallow => false,
1425                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
1426             });
1427
1428             self.access_place(
1429                 ContextKind::Activation.new(location),
1430                 (&borrow.borrowed_place, span),
1431                 (
1432                     Deep,
1433                     Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
1434                 ),
1435                 LocalMutationIsAllowed::No,
1436                 flow_state,
1437             );
1438             // We do not need to call `check_if_path_or_subpath_is_moved`
1439             // again, as we already called it when we made the
1440             // initial reservation.
1441         }
1442     }
1443 }
1444
1445 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
1446     fn check_if_reassignment_to_immutable_state(
1447         &mut self,
1448         context: Context,
1449         local: Local,
1450         place_span: (&Place<'tcx>, Span),
1451         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1452     ) {
1453         debug!("check_if_reassignment_to_immutable_state({:?})", local);
1454
1455         // Check if any of the initializiations of `local` have happened yet:
1456         if let Some(init_index) = self.is_local_ever_initialized(local, flow_state) {
1457             // And, if so, report an error.
1458             let init = &self.move_data.inits[init_index];
1459             let span = init.span(&self.mir);
1460             self.report_illegal_reassignment(
1461                 context, place_span, span, place_span.0
1462             );
1463         }
1464     }
1465
1466     fn check_if_full_path_is_moved(
1467         &mut self,
1468         context: Context,
1469         desired_action: InitializationRequiringAction,
1470         place_span: (&Place<'tcx>, Span),
1471         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1472     ) {
1473         let maybe_uninits = &flow_state.uninits;
1474
1475         // Bad scenarios:
1476         //
1477         // 1. Move of `a.b.c`, use of `a.b.c`
1478         // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
1479         // 3. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
1480         //    partial initialization support, one might have `a.x`
1481         //    initialized but not `a.b`.
1482         //
1483         // OK scenarios:
1484         //
1485         // 4. Move of `a.b.c`, use of `a.b.d`
1486         // 5. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1487         // 6. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1488         //    must have been initialized for the use to be sound.
1489         // 7. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1490
1491         // The dataflow tracks shallow prefixes distinctly (that is,
1492         // field-accesses on P distinctly from P itself), in order to
1493         // track substructure initialization separately from the whole
1494         // structure.
1495         //
1496         // E.g., when looking at (*a.b.c).d, if the closest prefix for
1497         // which we have a MovePath is `a.b`, then that means that the
1498         // initialization state of `a.b` is all we need to inspect to
1499         // know if `a.b.c` is valid (and from that we infer that the
1500         // dereference and `.d` access is also valid, since we assume
1501         // `a.b.c` is assigned a reference to a initialized and
1502         // well-formed record structure.)
1503
1504         // Therefore, if we seek out the *closest* prefix for which we
1505         // have a MovePath, that should capture the initialization
1506         // state for the place scenario.
1507         //
1508         // This code covers scenarios 1, 2, and 3.
1509
1510         debug!("check_if_full_path_is_moved place: {:?}", place_span.0);
1511         match self.move_path_closest_to(place_span.0) {
1512             Ok((prefix, mpi)) => {
1513                 if maybe_uninits.contains(mpi) {
1514                     self.report_use_of_moved_or_uninitialized(
1515                         context,
1516                         desired_action,
1517                         (prefix, place_span.0, place_span.1),
1518                         mpi,
1519                     );
1520                     return; // don't bother finding other problems.
1521                 }
1522             }
1523             Err(NoMovePathFound::ReachedStatic) => {
1524                 // Okay: we do not build MoveData for static variables
1525             } // Only query longest prefix with a MovePath, not further
1526               // ancestors; dataflow recurs on children when parents
1527               // move (to support partial (re)inits).
1528               //
1529               // (I.e. querying parents breaks scenario 7; but may want
1530               // to do such a query based on partial-init feature-gate.)
1531         }
1532     }
1533
1534     fn check_if_path_or_subpath_is_moved(
1535         &mut self,
1536         context: Context,
1537         desired_action: InitializationRequiringAction,
1538         place_span: (&Place<'tcx>, Span),
1539         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1540     ) {
1541         let maybe_uninits = &flow_state.uninits;
1542
1543         // Bad scenarios:
1544         //
1545         // 1. Move of `a.b.c`, use of `a` or `a.b`
1546         //    partial initialization support, one might have `a.x`
1547         //    initialized but not `a.b`.
1548         // 2. All bad scenarios from `check_if_full_path_is_moved`
1549         //
1550         // OK scenarios:
1551         //
1552         // 3. Move of `a.b.c`, use of `a.b.d`
1553         // 4. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1554         // 5. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1555         //    must have been initialized for the use to be sound.
1556         // 6. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1557
1558         self.check_if_full_path_is_moved(context, desired_action, place_span, flow_state);
1559
1560         // A move of any shallow suffix of `place` also interferes
1561         // with an attempt to use `place`. This is scenario 3 above.
1562         //
1563         // (Distinct from handling of scenarios 1+2+4 above because
1564         // `place` does not interfere with suffixes of its prefixes,
1565         // e.g. `a.b.c` does not interfere with `a.b.d`)
1566         //
1567         // This code covers scenario 1.
1568
1569         debug!("check_if_path_or_subpath_is_moved place: {:?}", place_span.0);
1570         if let Some(mpi) = self.move_path_for_place(place_span.0) {
1571             if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) {
1572                 self.report_use_of_moved_or_uninitialized(
1573                     context,
1574                     desired_action,
1575                     (place_span.0, place_span.0, place_span.1),
1576                     child_mpi,
1577                 );
1578                 return; // don't bother finding other problems.
1579             }
1580         }
1581     }
1582
1583     /// Currently MoveData does not store entries for all places in
1584     /// the input MIR. For example it will currently filter out
1585     /// places that are Copy; thus we do not track places of shared
1586     /// reference type. This routine will walk up a place along its
1587     /// prefixes, searching for a foundational place that *is*
1588     /// tracked in the MoveData.
1589     ///
1590     /// An Err result includes a tag indicated why the search failed.
1591     /// Currently this can only occur if the place is built off of a
1592     /// static variable, as we do not track those in the MoveData.
1593     fn move_path_closest_to<'a>(
1594         &mut self,
1595         place: &'a Place<'tcx>,
1596     ) -> Result<(&'a Place<'tcx>, MovePathIndex), NoMovePathFound> where 'cx: 'a {
1597         let mut last_prefix = place;
1598         for prefix in self.prefixes(place, PrefixSet::All) {
1599             if let Some(mpi) = self.move_path_for_place(prefix) {
1600                 return Ok((prefix, mpi));
1601             }
1602             last_prefix = prefix;
1603         }
1604         match *last_prefix {
1605             Place::Local(_) => panic!("should have move path for every Local"),
1606             Place::Projection(_) => panic!("PrefixSet::All meant don't stop for Projection"),
1607             Place::Promoted(_) |
1608             Place::Static(_) => Err(NoMovePathFound::ReachedStatic),
1609         }
1610     }
1611
1612     fn move_path_for_place(&mut self, place: &Place<'tcx>) -> Option<MovePathIndex> {
1613         // If returns None, then there is no move path corresponding
1614         // to a direct owner of `place` (which means there is nothing
1615         // that borrowck tracks for its analysis).
1616
1617         match self.move_data.rev_lookup.find(place) {
1618             LookupResult::Parent(_) => None,
1619             LookupResult::Exact(mpi) => Some(mpi),
1620         }
1621     }
1622
1623     fn check_if_assigned_path_is_moved(
1624         &mut self,
1625         context: Context,
1626         (place, span): (&Place<'tcx>, Span),
1627         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1628     ) {
1629         debug!("check_if_assigned_path_is_moved place: {:?}", place);
1630         // recur down place; dispatch to external checks when necessary
1631         let mut place = place;
1632         loop {
1633             match *place {
1634                 Place::Promoted(_) |
1635                 Place::Local(_) | Place::Static(_) => {
1636                     // assigning to `x` does not require `x` be initialized.
1637                     break;
1638                 }
1639                 Place::Projection(ref proj) => {
1640                     let Projection { ref base, ref elem } = **proj;
1641                     match *elem {
1642                         ProjectionElem::Index(_/*operand*/) |
1643                         ProjectionElem::ConstantIndex { .. } |
1644                         // assigning to P[i] requires P to be valid.
1645                         ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
1646                         // assigning to (P->variant) is okay if assigning to `P` is okay
1647                         //
1648                         // FIXME: is this true even if P is a adt with a dtor?
1649                         { }
1650
1651                         // assigning to (*P) requires P to be initialized
1652                         ProjectionElem::Deref => {
1653                             self.check_if_full_path_is_moved(
1654                                 context, InitializationRequiringAction::Use,
1655                                 (base, span), flow_state);
1656                             // (base initialized; no need to
1657                             // recur further)
1658                             break;
1659                         }
1660
1661                         ProjectionElem::Subslice { .. } => {
1662                             panic!("we don't allow assignments to subslices, context: {:?}",
1663                                    context);
1664                         }
1665
1666                         ProjectionElem::Field(..) => {
1667                             // if type of `P` has a dtor, then
1668                             // assigning to `P.f` requires `P` itself
1669                             // be already initialized
1670                             let tcx = self.infcx.tcx;
1671                             match base.ty(self.mir, tcx).to_ty(tcx).sty {
1672                                 ty::Adt(def, _) if def.has_dtor(tcx) => {
1673                                     self.check_if_path_or_subpath_is_moved(
1674                                         context, InitializationRequiringAction::Assignment,
1675                                         (base, span), flow_state);
1676
1677                                     // (base initialized; no need to
1678                                     // recur further)
1679                                     break;
1680                                 }
1681
1682
1683                                 // Once `let s; s.x = V; read(s.x);`,
1684                                 // is allowed, remove this match arm.
1685                                 ty::Adt(..) | ty::Tuple(..) => {
1686                                     check_parent_of_field(self, context, base, span, flow_state);
1687
1688                                     if let Some(local) = place.base_local() {
1689                                         // rust-lang/rust#21232,
1690                                         // #54499, #54986: during
1691                                         // period where we reject
1692                                         // partial initialization, do
1693                                         // not complain about
1694                                         // unnecessary `mut` on an
1695                                         // attempt to do a partial
1696                                         // initialization.
1697                                         self.used_mut.insert(local);
1698                                     }
1699                                 }
1700
1701                                 _ => {}
1702                             }
1703                         }
1704                     }
1705
1706                     place = base;
1707                     continue;
1708                 }
1709             }
1710         }
1711
1712         fn check_parent_of_field<'cx, 'gcx, 'tcx>(
1713             this: &mut MirBorrowckCtxt<'cx, 'gcx, 'tcx>,
1714             context: Context,
1715             base: &Place<'tcx>,
1716             span: Span,
1717             flow_state: &Flows<'cx, 'gcx, 'tcx>,
1718         ) {
1719             // rust-lang/rust#21232: Until Rust allows reads from the
1720             // initialized parts of partially initialized structs, we
1721             // will, starting with the 2018 edition, reject attempts
1722             // to write to structs that are not fully initialized.
1723             //
1724             // In other words, *until* we allow this:
1725             //
1726             // 1. `let mut s; s.x = Val; read(s.x);`
1727             //
1728             // we will for now disallow this:
1729             //
1730             // 2. `let mut s; s.x = Val;`
1731             //
1732             // and also this:
1733             //
1734             // 3. `let mut s = ...; drop(s); s.x=Val;`
1735             //
1736             // This does not use check_if_path_or_subpath_is_moved,
1737             // because we want to *allow* reinitializations of fields:
1738             // e.g. want to allow
1739             //
1740             // `let mut s = ...; drop(s.x); s.x=Val;`
1741             //
1742             // This does not use check_if_full_path_is_moved on
1743             // `base`, because that would report an error about the
1744             // `base` as a whole, but in this scenario we *really*
1745             // want to report an error about the actual thing that was
1746             // moved, which may be some prefix of `base`.
1747
1748             // Shallow so that we'll stop at any dereference; we'll
1749             // report errors about issues with such bases elsewhere.
1750             let maybe_uninits = &flow_state.uninits;
1751
1752             // Find the shortest uninitialized prefix you can reach
1753             // without going over a Deref.
1754             let mut shortest_uninit_seen = None;
1755             for prefix in this.prefixes(base, PrefixSet::Shallow) {
1756                 let mpi = match this.move_path_for_place(prefix) {
1757                     Some(mpi) => mpi, None => continue,
1758                 };
1759
1760                 if maybe_uninits.contains(mpi) {
1761                     debug!("check_parent_of_field updating shortest_uninit_seen from {:?} to {:?}",
1762                            shortest_uninit_seen, Some((prefix, mpi)));
1763                     shortest_uninit_seen = Some((prefix, mpi));
1764                 } else {
1765                     debug!("check_parent_of_field {:?} is definitely initialized", (prefix, mpi));
1766                 }
1767             }
1768
1769             if let Some((prefix, mpi)) = shortest_uninit_seen {
1770                 // Check for a reassignment into a uninitialized field of a union (for example,
1771                 // after a move out). In this case, do not report a error here. There is an
1772                 // exception, if this is the first assignment into the union (that is, there is
1773                 // no move out from an earlier location) then this is an attempt at initialization
1774                 // of the union - we should error in that case.
1775                 let tcx = this.infcx.tcx;
1776                 if let ty::TyKind::Adt(def, _) = base.ty(this.mir, tcx).to_ty(tcx).sty {
1777                     if def.is_union() {
1778                         if this.move_data.path_map[mpi].iter().any(|moi| {
1779                             this.move_data.moves[*moi].source.is_predecessor_of(
1780                                 context.loc, this.mir,
1781                             )
1782                         }) {
1783                             return;
1784                         }
1785                     }
1786                 }
1787
1788                 this.report_use_of_moved_or_uninitialized(
1789                     context,
1790                     InitializationRequiringAction::PartialAssignment,
1791                     (prefix, base, span),
1792                     mpi,
1793                 );
1794             }
1795         }
1796     }
1797
1798     /// Check the permissions for the given place and read or write kind
1799     ///
1800     /// Returns true if an error is reported, false otherwise.
1801     fn check_access_permissions(
1802         &mut self,
1803         (place, span): (&Place<'tcx>, Span),
1804         kind: ReadOrWrite,
1805         is_local_mutation_allowed: LocalMutationIsAllowed,
1806         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1807         location: Location,
1808     ) -> bool {
1809         debug!(
1810             "check_access_permissions({:?}, {:?}, is_local_mutation_allowed: {:?})",
1811             place, kind, is_local_mutation_allowed
1812         );
1813
1814         let error_access;
1815         let the_place_err;
1816
1817         // rust-lang/rust#21232, #54986: during period where we reject
1818         // partial initialization, do not complain about mutability
1819         // errors except for actual mutation (as opposed to an attempt
1820         // to do a partial initialization).
1821         let previously_initialized = if let Some(local) = place.base_local() {
1822             self.is_local_ever_initialized(local, flow_state).is_some()
1823         } else {
1824             true
1825         };
1826
1827         match kind {
1828             Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1829             | Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. }))
1830             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1831             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. })) => {
1832                 let is_local_mutation_allowed = match borrow_kind {
1833                     BorrowKind::Unique => LocalMutationIsAllowed::Yes,
1834                     BorrowKind::Mut { .. } => is_local_mutation_allowed,
1835                     BorrowKind::Shared | BorrowKind::Shallow => unreachable!(),
1836                 };
1837                 match self.is_mutable(place, is_local_mutation_allowed) {
1838                     Ok(root_place) => {
1839                         self.add_used_mut(root_place, flow_state);
1840                         return false;
1841                     }
1842                     Err(place_err) => {
1843                         error_access = AccessKind::MutableBorrow;
1844                         the_place_err = place_err;
1845                     }
1846                 }
1847             }
1848             Reservation(WriteKind::Mutate) | Write(WriteKind::Mutate) => {
1849                 match self.is_mutable(place, is_local_mutation_allowed) {
1850                     Ok(root_place) => {
1851                         self.add_used_mut(root_place, flow_state);
1852                         return false;
1853                     }
1854                     Err(place_err) => {
1855                         error_access = AccessKind::Mutate;
1856                         the_place_err = place_err;
1857                     }
1858                 }
1859             }
1860
1861             Reservation(wk @ WriteKind::Move)
1862             | Write(wk @ WriteKind::Move)
1863             | Reservation(wk @ WriteKind::StorageDeadOrDrop)
1864             | Reservation(wk @ WriteKind::MutableBorrow(BorrowKind::Shared))
1865             | Reservation(wk @ WriteKind::MutableBorrow(BorrowKind::Shallow))
1866             | Write(wk @ WriteKind::StorageDeadOrDrop)
1867             | Write(wk @ WriteKind::MutableBorrow(BorrowKind::Shared))
1868             | Write(wk @ WriteKind::MutableBorrow(BorrowKind::Shallow)) => {
1869                 if let (Err(_place_err), true) = (
1870                     self.is_mutable(place, is_local_mutation_allowed),
1871                     self.errors_buffer.is_empty()
1872                 ) {
1873                     if self.infcx.tcx.migrate_borrowck() {
1874                         // rust-lang/rust#46908: In pure NLL mode this
1875                         // code path should be unreachable (and thus
1876                         // we signal an ICE in the else branch
1877                         // here). But we can legitimately get here
1878                         // under borrowck=migrate mode, so instead of
1879                         // ICE'ing we instead report a legitimate
1880                         // error (which will then be downgraded to a
1881                         // warning by the migrate machinery).
1882                         error_access = match wk {
1883                             WriteKind::MutableBorrow(_) => AccessKind::MutableBorrow,
1884                             WriteKind::Move => AccessKind::Move,
1885                             WriteKind::StorageDeadOrDrop |
1886                             WriteKind::Mutate => AccessKind::Mutate,
1887                         };
1888                         self.report_mutability_error(
1889                             place,
1890                             span,
1891                             _place_err,
1892                             error_access,
1893                             location,
1894                         );
1895                     } else {
1896                         span_bug!(
1897                             span,
1898                             "Accessing `{:?}` with the kind `{:?}` shouldn't be possible",
1899                             place,
1900                             kind,
1901                         );
1902                     }
1903                 }
1904                 return false;
1905             }
1906             Activation(..) => {
1907                 // permission checks are done at Reservation point.
1908                 return false;
1909             }
1910             Read(ReadKind::Borrow(BorrowKind::Unique))
1911             | Read(ReadKind::Borrow(BorrowKind::Mut { .. }))
1912             | Read(ReadKind::Borrow(BorrowKind::Shared))
1913             | Read(ReadKind::Borrow(BorrowKind::Shallow))
1914             | Read(ReadKind::Copy) => {
1915                 // Access authorized
1916                 return false;
1917             }
1918         }
1919
1920         // at this point, we have set up the error reporting state.
1921         return if previously_initialized {
1922             self.report_mutability_error(
1923                 place,
1924                 span,
1925                 the_place_err,
1926                 error_access,
1927                 location,
1928             );
1929             true
1930         } else {
1931             false
1932         };
1933     }
1934
1935     fn is_local_ever_initialized(&self,
1936                                  local: Local,
1937                                  flow_state: &Flows<'cx, 'gcx, 'tcx>)
1938                                  -> Option<InitIndex>
1939     {
1940         let mpi = self.move_data.rev_lookup.find_local(local);
1941         let ii = &self.move_data.init_path_map[mpi];
1942         for &index in ii {
1943             if flow_state.ever_inits.contains(index) {
1944                 return Some(index);
1945             }
1946         }
1947         None
1948     }
1949
1950     /// Adds the place into the used mutable variables set
1951     fn add_used_mut<'d>(
1952         &mut self,
1953         root_place: RootPlace<'d, 'tcx>,
1954         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1955     ) {
1956         match root_place {
1957             RootPlace {
1958                 place: Place::Local(local),
1959                 is_local_mutation_allowed,
1960             } => {
1961                 // If the local may have been initialized, and it is now currently being
1962                 // mutated, then it is justified to be annotated with the `mut`
1963                 // keyword, since the mutation may be a possible reassignment.
1964                 if is_local_mutation_allowed != LocalMutationIsAllowed::Yes &&
1965                     self.is_local_ever_initialized(*local, flow_state).is_some()
1966                 {
1967                     self.used_mut.insert(*local);
1968                 }
1969             }
1970             RootPlace {
1971                 place: _,
1972                 is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1973             } => {}
1974             RootPlace {
1975                 place: place @ Place::Projection(_),
1976                 is_local_mutation_allowed: _,
1977             } => {
1978                 if let Some(field) = place.is_upvar_field_projection(self.mir, &self.infcx.tcx) {
1979                     self.used_mut_upvars.push(field);
1980                 }
1981             }
1982             RootPlace {
1983                 place: Place::Promoted(..),
1984                 is_local_mutation_allowed: _,
1985             } => {}
1986             RootPlace {
1987                 place: Place::Static(..),
1988                 is_local_mutation_allowed: _,
1989             } => {}
1990         }
1991     }
1992
1993     /// Whether this value can be written or borrowed mutably.
1994     /// Returns the root place if the place passed in is a projection.
1995     fn is_mutable<'d>(
1996         &self,
1997         place: &'d Place<'tcx>,
1998         is_local_mutation_allowed: LocalMutationIsAllowed,
1999     ) -> Result<RootPlace<'d, 'tcx>, &'d Place<'tcx>> {
2000         match *place {
2001             Place::Local(local) => {
2002                 let local = &self.mir.local_decls[local];
2003                 match local.mutability {
2004                     Mutability::Not => match is_local_mutation_allowed {
2005                         LocalMutationIsAllowed::Yes => Ok(RootPlace {
2006                             place,
2007                             is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
2008                         }),
2009                         LocalMutationIsAllowed::ExceptUpvars => Ok(RootPlace {
2010                             place,
2011                             is_local_mutation_allowed: LocalMutationIsAllowed::ExceptUpvars,
2012                         }),
2013                         LocalMutationIsAllowed::No => Err(place),
2014                     },
2015                     Mutability::Mut => Ok(RootPlace {
2016                         place,
2017                         is_local_mutation_allowed,
2018                     }),
2019                 }
2020             }
2021             // The rules for promotion are made by `qualify_consts`, there wouldn't even be a
2022             // `Place::Promoted` if the promotion weren't 100% legal. So we just forward this
2023             Place::Promoted(_) => Ok(RootPlace {
2024                 place,
2025                 is_local_mutation_allowed,
2026             }),
2027             Place::Static(ref static_) => {
2028                 if self.infcx.tcx.is_static(static_.def_id) != Some(hir::Mutability::MutMutable) {
2029                     Err(place)
2030                 } else {
2031                     Ok(RootPlace {
2032                         place,
2033                         is_local_mutation_allowed,
2034                     })
2035                 }
2036             }
2037             Place::Projection(ref proj) => {
2038                 match proj.elem {
2039                     ProjectionElem::Deref => {
2040                         let base_ty = proj.base.ty(self.mir, self.infcx.tcx).to_ty(self.infcx.tcx);
2041
2042                         // Check the kind of deref to decide
2043                         match base_ty.sty {
2044                             ty::Ref(_, _, mutbl) => {
2045                                 match mutbl {
2046                                     // Shared borrowed data is never mutable
2047                                     hir::MutImmutable => Err(place),
2048                                     // Mutably borrowed data is mutable, but only if we have a
2049                                     // unique path to the `&mut`
2050                                     hir::MutMutable => {
2051                                         let mode = match place.is_upvar_field_projection(
2052                                             self.mir, &self.infcx.tcx)
2053                                         {
2054                                             Some(field)
2055                                                 if {
2056                                                     self.mir.upvar_decls[field.index()].by_ref
2057                                                 } =>
2058                                             {
2059                                                 is_local_mutation_allowed
2060                                             }
2061                                             _ => LocalMutationIsAllowed::Yes,
2062                                         };
2063
2064                                         self.is_mutable(&proj.base, mode)
2065                                     }
2066                                 }
2067                             }
2068                             ty::RawPtr(tnm) => {
2069                                 match tnm.mutbl {
2070                                     // `*const` raw pointers are not mutable
2071                                     hir::MutImmutable => Err(place),
2072                                     // `*mut` raw pointers are always mutable, regardless of
2073                                     // context. The users have to check by themselves.
2074                                     hir::MutMutable => {
2075                                         Ok(RootPlace {
2076                                             place,
2077                                             is_local_mutation_allowed,
2078                                         })
2079                                     }
2080                                 }
2081                             }
2082                             // `Box<T>` owns its content, so mutable if its location is mutable
2083                             _ if base_ty.is_box() => {
2084                                 self.is_mutable(&proj.base, is_local_mutation_allowed)
2085                             }
2086                             // Deref should only be for reference, pointers or boxes
2087                             _ => bug!("Deref of unexpected type: {:?}", base_ty),
2088                         }
2089                     }
2090                     // All other projections are owned by their base path, so mutable if
2091                     // base path is mutable
2092                     ProjectionElem::Field(..)
2093                     | ProjectionElem::Index(..)
2094                     | ProjectionElem::ConstantIndex { .. }
2095                     | ProjectionElem::Subslice { .. }
2096                     | ProjectionElem::Downcast(..) => {
2097                         let upvar_field_projection = place.is_upvar_field_projection(
2098                             self.mir, &self.infcx.tcx);
2099                         if let Some(field) = upvar_field_projection {
2100                             let decl = &self.mir.upvar_decls[field.index()];
2101                             debug!(
2102                                 "decl.mutability={:?} local_mutation_is_allowed={:?} place={:?}",
2103                                 decl, is_local_mutation_allowed, place
2104                             );
2105                             match (decl.mutability, is_local_mutation_allowed) {
2106                                 (Mutability::Not, LocalMutationIsAllowed::No)
2107                                 | (Mutability::Not, LocalMutationIsAllowed::ExceptUpvars) => {
2108                                     Err(place)
2109                                 }
2110                                 (Mutability::Not, LocalMutationIsAllowed::Yes)
2111                                 | (Mutability::Mut, _) => {
2112                                     // Subtle: this is an upvar
2113                                     // reference, so it looks like
2114                                     // `self.foo` -- we want to double
2115                                     // check that the context `*self`
2116                                     // is mutable (i.e., this is not a
2117                                     // `Fn` closure).  But if that
2118                                     // check succeeds, we want to
2119                                     // *blame* the mutability on
2120                                     // `place` (that is,
2121                                     // `self.foo`). This is used to
2122                                     // propagate the info about
2123                                     // whether mutability declarations
2124                                     // are used outwards, so that we register
2125                                     // the outer variable as mutable. Otherwise a
2126                                     // test like this fails to record the `mut`
2127                                     // as needed:
2128                                     //
2129                                     // ```
2130                                     // fn foo<F: FnOnce()>(_f: F) { }
2131                                     // fn main() {
2132                                     //     let var = Vec::new();
2133                                     //     foo(move || {
2134                                     //         var.push(1);
2135                                     //     });
2136                                     // }
2137                                     // ```
2138                                     let _ = self.is_mutable(&proj.base, is_local_mutation_allowed)?;
2139                                     Ok(RootPlace {
2140                                         place,
2141                                         is_local_mutation_allowed,
2142                                     })
2143                                 }
2144                             }
2145                         } else {
2146                             self.is_mutable(&proj.base, is_local_mutation_allowed)
2147                         }
2148                     }
2149                 }
2150             }
2151         }
2152     }
2153 }
2154
2155 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2156 enum NoMovePathFound {
2157     ReachedStatic,
2158 }
2159
2160 /// The degree of overlap between 2 places for borrow-checking.
2161 enum Overlap {
2162     /// The places might partially overlap - in this case, we give
2163     /// up and say that they might conflict. This occurs when
2164     /// different fields of a union are borrowed. For example,
2165     /// if `u` is a union, we have no way of telling how disjoint
2166     /// `u.a.x` and `a.b.y` are.
2167     Arbitrary,
2168     /// The places have the same type, and are either completely disjoint
2169     /// or equal - i.e. they can't "partially" overlap as can occur with
2170     /// unions. This is the "base case" on which we recur for extensions
2171     /// of the place.
2172     EqualOrDisjoint,
2173     /// The places are disjoint, so we know all extensions of them
2174     /// will also be disjoint.
2175     Disjoint,
2176 }
2177
2178 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2179 struct Context {
2180     kind: ContextKind,
2181     loc: Location,
2182 }
2183
2184 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2185 enum ContextKind {
2186     Activation,
2187     AssignLhs,
2188     AssignRhs,
2189     SetDiscrim,
2190     InlineAsm,
2191     SwitchInt,
2192     Drop,
2193     DropAndReplace,
2194     CallOperator,
2195     CallOperand,
2196     CallDest,
2197     Assert,
2198     Yield,
2199     FakeRead,
2200     StorageDead,
2201 }
2202
2203 impl ContextKind {
2204     fn new(self, loc: Location) -> Context {
2205         Context {
2206             kind: self,
2207             loc,
2208         }
2209     }
2210 }