src/librustc_mir/borrow_check/mod.rs

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