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