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(ref asm) => {
 529                 let context = ContextKind::InlineAsm.new(location);
 530                 for (o, output) in asm.asm.outputs.iter().zip(asm.outputs.iter()) {
 531                     if o.is_indirect {
 532                         // FIXME(eddyb) indirect inline asm outputs should
 533                         // be encoded through MIR place derefs instead.
 534                         self.access_place(
 535                             context,
 536                             (output, o.span),
 537                             (Deep, Read(ReadKind::Copy)),
 538                             LocalMutationIsAllowed::No,
 539                             flow_state,
 540                         );
 541                         self.check_if_path_or_subpath_is_moved(
 542                             context,
 543                             InitializationRequiringAction::Use,
 544                             (output, o.span),
 545                             flow_state,
 546                         );
 547                     } else {
 548                         self.mutate_place(
 549                             context,
 550                             (output, o.span),
 551                             if o.is_rw { Deep } else { Shallow(None) },
 552                             if o.is_rw { WriteAndRead } else { JustWrite },
 553                             flow_state,
 554                         );
 555                     }
 556                 }
 557                 for (_, input) in asm.inputs.iter() {
 558                     self.consume_operand(context, (input, span), flow_state);
 559                 }
 560             }
 561             StatementKind::Nop
 562             | StatementKind::AscribeUserType(..)
 563             | StatementKind::Retag { .. }
 564             | StatementKind::StorageLive(..) => {
 565                 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
 566                 // to borrow check.
 567             }
 568             StatementKind::StorageDead(local) => {
 569                 self.access_place(
 570                     ContextKind::StorageDead.new(location),
 571                     (&Place::Base(PlaceBase::Local(local)), span),
 572                     (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
 573                     LocalMutationIsAllowed::Yes,
 574                     flow_state,
 575                 );
 576             }
 577         }
 578     }
 579
 580     fn visit_terminator_entry(
 581         &mut self,
 582         location: Location,
 583         term: &Terminator<'tcx>,
 584         flow_state: &Self::FlowState,
 585     ) {
 586         let loc = location;
 587         debug!(
 588             "MirBorrowckCtxt::process_terminator({:?}, {:?}): {}",
 589             location, term, flow_state
 590         );
 591         let span = term.source_info.span;
 592
 593         self.check_activations(location, span, flow_state);
 594
 595         match term.kind {
 596             TerminatorKind::SwitchInt {
 597                 ref discr,
 598                 switch_ty: _,
 599                 values: _,
 600                 targets: _,
 601             } => {
 602                 self.consume_operand(ContextKind::SwitchInt.new(loc), (discr, span), flow_state);
 603             }
 604             TerminatorKind::Drop {
 605                 location: ref drop_place,
 606                 target: _,
 607                 unwind: _,
 608             } => {
 609                 let gcx = self.infcx.tcx.global_tcx();
 610
 611                 // Compute the type with accurate region information.
 612                 let drop_place_ty = drop_place.ty(self.mir, self.infcx.tcx);
 613
 614                 // Erase the regions.
 615                 let drop_place_ty = self.infcx.tcx.erase_regions(&drop_place_ty).ty;
 616
 617                 // "Lift" into the gcx -- once regions are erased, this type should be in the
 618                 // global arenas; this "lift" operation basically just asserts that is true, but
 619                 // that is useful later.
 620                 let drop_place_ty = gcx.lift(&drop_place_ty).unwrap();
 621
 622                 debug!("visit_terminator_drop \
 623                         loc: {:?} term: {:?} drop_place: {:?} drop_place_ty: {:?} span: {:?}",
 624                        loc, term, drop_place, drop_place_ty, span);
 625
 626                 self.access_place(
 627                     ContextKind::Drop.new(loc),
 628                     (drop_place, span),
 629                     (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
 630                     LocalMutationIsAllowed::Yes,
 631                     flow_state,
 632                 );
 633             }
 634             TerminatorKind::DropAndReplace {
 635                 location: ref drop_place,
 636                 value: ref new_value,
 637                 target: _,
 638                 unwind: _,
 639             } => {
 640                 self.mutate_place(
 641                     ContextKind::DropAndReplace.new(loc),
 642                     (drop_place, span),
 643                     Deep,
 644                     JustWrite,
 645                     flow_state,
 646                 );
 647                 self.consume_operand(
 648                     ContextKind::DropAndReplace.new(loc),
 649                     (new_value, span),
 650                     flow_state,
 651                 );
 652             }
 653             TerminatorKind::Call {
 654                 ref func,
 655                 ref args,
 656                 ref destination,
 657                 cleanup: _,
 658                 from_hir_call: _,
 659             } => {
 660                 self.consume_operand(ContextKind::CallOperator.new(loc), (func, span), flow_state);
 661                 for arg in args {
 662                     self.consume_operand(
 663                         ContextKind::CallOperand.new(loc),
 664                         (arg, span),
 665                         flow_state,
 666                     );
 667                 }
 668                 if let Some((ref dest, _ /*bb*/)) = *destination {
 669                     self.mutate_place(
 670                         ContextKind::CallDest.new(loc),
 671                         (dest, span),
 672                         Deep,
 673                         JustWrite,
 674                         flow_state,
 675                     );
 676                 }
 677             }
 678             TerminatorKind::Assert {
 679                 ref cond,
 680                 expected: _,
 681                 ref msg,
 682                 target: _,
 683                 cleanup: _,
 684             } => {
 685                 self.consume_operand(ContextKind::Assert.new(loc), (cond, span), flow_state);
 686                 use rustc::mir::interpret::InterpError::BoundsCheck;
 687                 if let BoundsCheck { ref len, ref index } = *msg {
 688                     self.consume_operand(ContextKind::Assert.new(loc), (len, span), flow_state);
 689                     self.consume_operand(ContextKind::Assert.new(loc), (index, span), flow_state);
 690                 }
 691             }
 692
 693             TerminatorKind::Yield {
 694                 ref value,
 695                 resume: _,
 696                 drop: _,
 697             } => {
 698                 self.consume_operand(ContextKind::Yield.new(loc), (value, span), flow_state);
 699
 700                 if self.movable_generator {
 701                     // Look for any active borrows to locals
 702                     let borrow_set = self.borrow_set.clone();
 703                     flow_state.with_outgoing_borrows(|borrows| {
 704                         for i in borrows {
 705                             let borrow = &borrow_set[i];
 706                             self.check_for_local_borrow(borrow, span);
 707                         }
 708                     });
 709                 }
 710             }
 711
 712             TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
 713                 // Returning from the function implicitly kills storage for all locals and statics.
 714                 // Often, the storage will already have been killed by an explicit
 715                 // StorageDead, but we don't always emit those (notably on unwind paths),
 716                 // so this "extra check" serves as a kind of backup.
 717                 let borrow_set = self.borrow_set.clone();
 718                 flow_state.with_outgoing_borrows(|borrows| {
 719                     for i in borrows {
 720                         let borrow = &borrow_set[i];
 721                         let context = ContextKind::StorageDead.new(loc);
 722                         self.check_for_invalidation_at_exit(context, borrow, span);
 723                     }
 724                 });
 725             }
 726             TerminatorKind::Goto { target: _ }
 727             | TerminatorKind::Abort
 728             | TerminatorKind::Unreachable
 729             | TerminatorKind::FalseEdges {
 730                 real_target: _,
 731                 imaginary_targets: _,
 732             }
 733             | TerminatorKind::FalseUnwind {
 734                 real_target: _,
 735                 unwind: _,
 736             } => {
 737                 // no data used, thus irrelevant to borrowck
 738             }
 739         }
 740     }
 741 }
 742
 743 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 744 enum MutateMode {
 745     JustWrite,
 746     WriteAndRead,
 747 }
 748
 749 use self::ReadOrWrite::{Activation, Read, Reservation, Write};
 750 use self::AccessDepth::{Deep, Shallow};
 751
 752 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 753 enum ArtificialField {
 754     ArrayLength,
 755     ShallowBorrow,
 756 }
 757
 758 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 759 enum AccessDepth {
 760     /// From the RFC: "A *shallow* access means that the immediate
 761     /// fields reached at P are accessed, but references or pointers
 762     /// found within are not dereferenced. Right now, the only access
 763     /// that is shallow is an assignment like `x = ...;`, which would
 764     /// be a *shallow write* of `x`."
 765     Shallow(Option<ArtificialField>),
 766
 767     /// From the RFC: "A *deep* access means that all data reachable
 768     /// through the given place may be invalidated or accesses by
 769     /// this action."
 770     Deep,
 771
 772     /// Access is Deep only when there is a Drop implementation that
 773     /// can reach the data behind the reference.
 774     Drop,
 775 }
 776
 777 /// Kind of access to a value: read or write
 778 /// (For informational purposes only)
 779 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 780 enum ReadOrWrite {
 781     /// From the RFC: "A *read* means that the existing data may be
 782     /// read, but will not be changed."
 783     Read(ReadKind),
 784
 785     /// From the RFC: "A *write* means that the data may be mutated to
 786     /// new values or otherwise invalidated (for example, it could be
 787     /// de-initialized, as in a move operation).
 788     Write(WriteKind),
 789
 790     /// For two-phase borrows, we distinguish a reservation (which is treated
 791     /// like a Read) from an activation (which is treated like a write), and
 792     /// each of those is furthermore distinguished from Reads/Writes above.
 793     Reservation(WriteKind),
 794     Activation(WriteKind, BorrowIndex),
 795 }
 796
 797 /// Kind of read access to a value
 798 /// (For informational purposes only)
 799 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 800 enum ReadKind {
 801     Borrow(BorrowKind),
 802     Copy,
 803 }
 804
 805 /// Kind of write access to a value
 806 /// (For informational purposes only)
 807 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 808 enum WriteKind {
 809     StorageDeadOrDrop,
 810     MutableBorrow(BorrowKind),
 811     Mutate,
 812     Move,
 813 }
 814
 815 /// When checking permissions for a place access, this flag is used to indicate that an immutable
 816 /// local place can be mutated.
 817 //
 818 // FIXME: @nikomatsakis suggested that this flag could be removed with the following modifications:
 819 // - Merge `check_access_permissions()` and `check_if_reassignment_to_immutable_state()`.
 820 // - Split `is_mutable()` into `is_assignable()` (can be directly assigned) and
 821 //   `is_declared_mutable()`.
 822 // - Take flow state into consideration in `is_assignable()` for local variables.
 823 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 824 enum LocalMutationIsAllowed {
 825     Yes,
 826     /// We want use of immutable upvars to cause a "write to immutable upvar"
 827     /// error, not an "reassignment" error.
 828     ExceptUpvars,
 829     No,
 830 }
 831
 832 #[derive(Copy, Clone, Debug)]
 833 enum InitializationRequiringAction {
 834     Update,
 835     Borrow,
 836     MatchOn,
 837     Use,
 838     Assignment,
 839     PartialAssignment,
 840 }
 841
 842 struct RootPlace<'d, 'tcx: 'd> {
 843     place: &'d Place<'tcx>,
 844     is_local_mutation_allowed: LocalMutationIsAllowed,
 845 }
 846
 847 impl InitializationRequiringAction {
 848     fn as_noun(self) -> &'static str {
 849         match self {
 850             InitializationRequiringAction::Update => "update",
 851             InitializationRequiringAction::Borrow => "borrow",
 852             InitializationRequiringAction::MatchOn => "use", // no good noun
 853             InitializationRequiringAction::Use => "use",
 854             InitializationRequiringAction::Assignment => "assign",
 855             InitializationRequiringAction::PartialAssignment => "assign to part",
 856         }
 857     }
 858
 859     fn as_verb_in_past_tense(self) -> &'static str {
 860         match self {
 861             InitializationRequiringAction::Update => "updated",
 862             InitializationRequiringAction::Borrow => "borrowed",
 863             InitializationRequiringAction::MatchOn => "matched on",
 864             InitializationRequiringAction::Use => "used",
 865             InitializationRequiringAction::Assignment => "assigned",
 866             InitializationRequiringAction::PartialAssignment => "partially assigned",
 867         }
 868     }
 869 }
 870
 871 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
 872     /// Checks an access to the given place to see if it is allowed. Examines the set of borrows
 873     /// that are in scope, as well as which paths have been initialized, to ensure that (a) the
 874     /// place is initialized and (b) it is not borrowed in some way that would prevent this
 875     /// access.
 876     ///
 877     /// Returns `true` if an error is reported.
 878     fn access_place(
 879         &mut self,
 880         context: Context,
 881         place_span: (&Place<'tcx>, Span),
 882         kind: (AccessDepth, ReadOrWrite),
 883         is_local_mutation_allowed: LocalMutationIsAllowed,
 884         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 885     ) {
 886         let (sd, rw) = kind;
 887
 888         if let Activation(_, borrow_index) = rw {
 889             if self.reservation_error_reported.contains(&place_span.0) {
 890                 debug!(
 891                     "skipping access_place for activation of invalid reservation \
 892                      place: {:?} borrow_index: {:?}",
 893                     place_span.0, borrow_index
 894                 );
 895                 return;
 896             }
 897         }
 898
 899         // Check is_empty() first because it's the common case, and doing that
 900         // way we avoid the clone() call.
 901         if !self.access_place_error_reported.is_empty() &&
 902            self
 903             .access_place_error_reported
 904             .contains(&(place_span.0.clone(), place_span.1))
 905         {
 906             debug!(
 907                 "access_place: suppressing error place_span=`{:?}` kind=`{:?}`",
 908                 place_span, kind
 909             );
 910             return;
 911         }
 912
 913         let mutability_error =
 914             self.check_access_permissions(
 915                 place_span,
 916                 rw,
 917                 is_local_mutation_allowed,
 918                 flow_state,
 919                 context.loc,
 920             );
 921         let conflict_error =
 922             self.check_access_for_conflict(context, place_span, sd, rw, flow_state);
 923
 924         if conflict_error || mutability_error {
 925             debug!(
 926                 "access_place: logging error place_span=`{:?}` kind=`{:?}`",
 927                 place_span, kind
 928             );
 929             self.access_place_error_reported
 930                 .insert((place_span.0.clone(), place_span.1));
 931         }
 932     }
 933
 934     fn check_access_for_conflict(
 935         &mut self,
 936         context: Context,
 937         place_span: (&Place<'tcx>, Span),
 938         sd: AccessDepth,
 939         rw: ReadOrWrite,
 940         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 941     ) -> bool {
 942         debug!(
 943             "check_access_for_conflict(context={:?}, place_span={:?}, sd={:?}, rw={:?})",
 944             context, place_span, sd, rw,
 945         );
 946
 947         let mut error_reported = false;
 948         let tcx = self.infcx.tcx;
 949         let mir = self.mir;
 950         let location = self.location_table.start_index(context.loc);
 951         let borrow_set = self.borrow_set.clone();
 952         each_borrow_involving_path(
 953             self,
 954             tcx,
 955             mir,
 956             context,
 957             (sd, place_span.0),
 958             &borrow_set,
 959             flow_state.borrows_in_scope(location),
 960             |this, borrow_index, borrow| match (rw, borrow.kind) {
 961                 // Obviously an activation is compatible with its own
 962                 // reservation (or even prior activating uses of same
 963                 // borrow); so don't check if they interfere.
 964                 //
 965                 // NOTE: *reservations* do conflict with themselves;
 966                 // thus aren't injecting unsoundenss w/ this check.)
 967                 (Activation(_, activating), _) if activating == borrow_index => {
 968                     debug!(
 969                         "check_access_for_conflict place_span: {:?} sd: {:?} rw: {:?} \
 970                          skipping {:?} b/c activation of same borrow_index",
 971                         place_span,
 972                         sd,
 973                         rw,
 974                         (borrow_index, borrow),
 975                     );
 976                     Control::Continue
 977                 }
 978
 979                 (Read(_), BorrowKind::Shared) | (Reservation(..), BorrowKind::Shared)
 980                 | (Read(_), BorrowKind::Shallow) | (Reservation(..), BorrowKind::Shallow)
 981                 | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Unique)
 982                 | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Mut { .. }) => {
 983                     Control::Continue
 984                 }
 985
 986                 (Write(WriteKind::Move), BorrowKind::Shallow) => {
 987                     // Handled by initialization checks.
 988                     Control::Continue
 989                 }
 990
 991                 (Read(kind), BorrowKind::Unique) | (Read(kind), BorrowKind::Mut { .. }) => {
 992                     // Reading from mere reservations of mutable-borrows is OK.
 993                     if !is_active(&this.dominators, borrow, context.loc) {
 994                         assert!(allow_two_phase_borrow(&this.infcx.tcx, borrow.kind));
 995                         return Control::Continue;
 996                     }
 997
 998                     error_reported = true;
 999                     match kind {
1000                         ReadKind::Copy  => {
1001                             this.report_use_while_mutably_borrowed(context, place_span, borrow)
1002                         }
1003                         ReadKind::Borrow(bk) => {
1004                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1005                         }
1006                     }
1007                     Control::Break
1008                 }
1009
1010                 (Reservation(kind), BorrowKind::Unique)
1011                 | (Reservation(kind), BorrowKind::Mut { .. })
1012                 | (Activation(kind, _), _)
1013                 | (Write(kind), _) => {
1014                     match rw {
1015                         Reservation(_) => {
1016                             debug!(
1017                                 "recording invalid reservation of \
1018                                  place: {:?}",
1019                                 place_span.0
1020                             );
1021                             this.reservation_error_reported.insert(place_span.0.clone());
1022                         }
1023                         Activation(_, activating) => {
1024                             debug!(
1025                                 "observing check_place for activation of \
1026                                  borrow_index: {:?}",
1027                                 activating
1028                             );
1029                         }
1030                         Read(..) | Write(..) => {}
1031                     }
1032
1033                     error_reported = true;
1034                     match kind {
1035                         WriteKind::MutableBorrow(bk) => {
1036                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1037                         }
1038                         WriteKind::StorageDeadOrDrop => {
1039                             this.report_borrowed_value_does_not_live_long_enough(
1040                                 context,
1041                                 borrow,
1042                                 place_span,
1043                                 Some(kind))
1044                         }
1045                         WriteKind::Mutate => {
1046                             this.report_illegal_mutation_of_borrowed(context, place_span, borrow)
1047                         }
1048                         WriteKind::Move => {
1049                             this.report_move_out_while_borrowed(context, place_span, &borrow)
1050                         }
1051                     }
1052                     Control::Break
1053                 }
1054             },
1055         );
1056
1057         error_reported
1058     }
1059
1060     fn mutate_place(
1061         &mut self,
1062         context: Context,
1063         place_span: (&Place<'tcx>, Span),
1064         kind: AccessDepth,
1065         mode: MutateMode,
1066         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1067     ) {
1068         // Write of P[i] or *P, or WriteAndRead of any P, requires P init'd.
1069         match mode {
1070             MutateMode::WriteAndRead => {
1071                 self.check_if_path_or_subpath_is_moved(
1072                     context,
1073                     InitializationRequiringAction::Update,
1074                     place_span,
1075                     flow_state,
1076                 );
1077             }
1078             MutateMode::JustWrite => {
1079                 self.check_if_assigned_path_is_moved(context, place_span, flow_state);
1080             }
1081         }
1082
1083         // Special case: you can assign a immutable local variable
1084         // (e.g., `x = ...`) so long as it has never been initialized
1085         // before (at this point in the flow).
1086         if let &Place::Base(PlaceBase::Local(local)) = place_span.0 {
1087             if let Mutability::Not = self.mir.local_decls[local].mutability {
1088                 // check for reassignments to immutable local variables
1089                 self.check_if_reassignment_to_immutable_state(
1090                     context,
1091                     local,
1092                     place_span,
1093                     flow_state,
1094                 );
1095                 return;
1096             }
1097         }
1098
1099         // Otherwise, use the normal access permission rules.
1100         self.access_place(
1101             context,
1102             place_span,
1103             (kind, Write(WriteKind::Mutate)),
1104             LocalMutationIsAllowed::No,
1105             flow_state,
1106         );
1107     }
1108
1109     fn consume_rvalue(
1110         &mut self,
1111         context: Context,
1112         (rvalue, span): (&Rvalue<'tcx>, Span),
1113         _location: Location,
1114         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1115     ) {
1116         match *rvalue {
1117             Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
1118                 let access_kind = match bk {
1119                     BorrowKind::Shallow => {
1120                         (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
1121                     },
1122                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
1123                     BorrowKind::Unique | BorrowKind::Mut { .. } => {
1124                         let wk = WriteKind::MutableBorrow(bk);
1125                         if allow_two_phase_borrow(&self.infcx.tcx, bk) {
1126                             (Deep, Reservation(wk))
1127                         } else {
1128                             (Deep, Write(wk))
1129                         }
1130                     }
1131                 };
1132
1133                 self.access_place(
1134                     context,
1135                     (place, span),
1136                     access_kind,
1137                     LocalMutationIsAllowed::No,
1138                     flow_state,
1139                 );
1140
1141                 let action = if bk == BorrowKind::Shallow {
1142                     InitializationRequiringAction::MatchOn
1143                 } else {
1144                     InitializationRequiringAction::Borrow
1145                 };
1146
1147                 self.check_if_path_or_subpath_is_moved(
1148                     context,
1149                     action,
1150                     (place, span),
1151                     flow_state,
1152                 );
1153             }
1154
1155             Rvalue::Use(ref operand)
1156             | Rvalue::Repeat(ref operand, _)
1157             | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
1158             | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
1159                 self.consume_operand(context, (operand, span), flow_state)
1160             }
1161
1162             Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
1163                 let af = match *rvalue {
1164                     Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
1165                     Rvalue::Discriminant(..) => None,
1166                     _ => unreachable!(),
1167                 };
1168                 self.access_place(
1169                     context,
1170                     (place, span),
1171                     (Shallow(af), Read(ReadKind::Copy)),
1172                     LocalMutationIsAllowed::No,
1173                     flow_state,
1174                 );
1175                 self.check_if_path_or_subpath_is_moved(
1176                     context,
1177                     InitializationRequiringAction::Use,
1178                     (place, span),
1179                     flow_state,
1180                 );
1181             }
1182
1183             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
1184             | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
1185                 self.consume_operand(context, (operand1, span), flow_state);
1186                 self.consume_operand(context, (operand2, span), flow_state);
1187             }
1188
1189             Rvalue::NullaryOp(_op, _ty) => {
1190                 // nullary ops take no dynamic input; no borrowck effect.
1191                 //
1192                 // FIXME: is above actually true? Do we want to track
1193                 // the fact that uninitialized data can be created via
1194                 // `NullOp::Box`?
1195             }
1196
1197             Rvalue::Aggregate(ref aggregate_kind, ref operands) => {
1198                 // We need to report back the list of mutable upvars that were
1199                 // moved into the closure and subsequently used by the closure,
1200                 // in order to populate our used_mut set.
1201                 match **aggregate_kind {
1202                     AggregateKind::Closure(def_id, _)
1203                     | AggregateKind::Generator(def_id, _, _) => {
1204                         let BorrowCheckResult {
1205                             used_mut_upvars, ..
1206                         } = self.infcx.tcx.mir_borrowck(def_id);
1207                         debug!("{:?} used_mut_upvars={:?}", def_id, used_mut_upvars);
1208                         for field in used_mut_upvars {
1209                             // This relies on the current way that by-value
1210                             // captures of a closure are copied/moved directly
1211                             // when generating MIR.
1212                             match operands[field.index()] {
1213                                 Operand::Move(Place::Base(PlaceBase::Local(local)))
1214                                 | Operand::Copy(Place::Base(PlaceBase::Local(local))) => {
1215                                     self.used_mut.insert(local);
1216                                 }
1217                                 Operand::Move(ref place @ Place::Projection(_))
1218                                 | Operand::Copy(ref place @ Place::Projection(_)) => {
1219                                     if let Some(field) = place.is_upvar_field_projection(
1220                                             self.mir, &self.infcx.tcx) {
1221                                         self.used_mut_upvars.push(field);
1222                                     }
1223                                 }
1224                                 Operand::Move(Place::Base(PlaceBase::Static(..)))
1225                                 | Operand::Copy(Place::Base(PlaceBase::Static(..)))
1226                                 | Operand::Constant(..) => {}
1227                             }
1228                         }
1229                     }
1230                     AggregateKind::Adt(..)
1231                     | AggregateKind::Array(..)
1232                     | AggregateKind::Tuple { .. } => (),
1233                 }
1234
1235                 for operand in operands {
1236                     self.consume_operand(context, (operand, span), flow_state);
1237                 }
1238             }
1239         }
1240     }
1241
1242     fn consume_operand(
1243         &mut self,
1244         context: Context,
1245         (operand, span): (&Operand<'tcx>, Span),
1246         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1247     ) {
1248         match *operand {
1249             Operand::Copy(ref place) => {
1250                 // copy of place: check if this is "copy of frozen path"
1251                 // (FIXME: see check_loans.rs)
1252                 self.access_place(
1253                     context,
1254                     (place, span),
1255                     (Deep, Read(ReadKind::Copy)),
1256                     LocalMutationIsAllowed::No,
1257                     flow_state,
1258                 );
1259
1260                 // Finally, check if path was already moved.
1261                 self.check_if_path_or_subpath_is_moved(
1262                     context,
1263                     InitializationRequiringAction::Use,
1264                     (place, span),
1265                     flow_state,
1266                 );
1267             }
1268             Operand::Move(ref place) => {
1269                 // move of place: check if this is move of already borrowed path
1270                 self.access_place(
1271                     context,
1272                     (place, span),
1273                     (Deep, Write(WriteKind::Move)),
1274                     LocalMutationIsAllowed::Yes,
1275                     flow_state,
1276                 );
1277
1278                 // Finally, check if path was already moved.
1279                 self.check_if_path_or_subpath_is_moved(
1280                     context,
1281                     InitializationRequiringAction::Use,
1282                     (place, span),
1283                     flow_state,
1284                 );
1285             }
1286             Operand::Constant(_) => {}
1287         }
1288     }
1289
1290     /// Checks whether a borrow of this place is invalidated when the function
1291     /// exits
1292     fn check_for_invalidation_at_exit(
1293         &mut self,
1294         context: Context,
1295         borrow: &BorrowData<'tcx>,
1296         span: Span,
1297     ) {
1298         debug!("check_for_invalidation_at_exit({:?})", borrow);
1299         let place = &borrow.borrowed_place;
1300         let root_place = self.prefixes(place, PrefixSet::All).last().unwrap();
1301
1302         // FIXME(nll-rfc#40): do more precise destructor tracking here. For now
1303         // we just know that all locals are dropped at function exit (otherwise
1304         // we'll have a memory leak) and assume that all statics have a destructor.
1305         //
1306         // FIXME: allow thread-locals to borrow other thread locals?
1307         let (might_be_alive, will_be_dropped) = match root_place {
1308             Place::Base(PlaceBase::Static(box Static{ kind: StaticKind::Promoted(_), .. })) => {
1309                 (true, false)
1310             }
1311             Place::Base(PlaceBase::Static(box Static{ kind: StaticKind::Static(_), .. })) => {
1312                 // Thread-locals might be dropped after the function exits, but
1313                 // "true" statics will never be.
1314                 (true, self.is_place_thread_local(&root_place))
1315             }
1316             Place::Base(PlaceBase::Local(_)) => {
1317                 // Locals are always dropped at function exit, and if they
1318                 // have a destructor it would've been called already.
1319                 (false, self.locals_are_invalidated_at_exit)
1320             }
1321             Place::Projection(..) => {
1322                 bug!("root of {:?} is a projection ({:?})?", place, root_place)
1323             }
1324         };
1325
1326         if !will_be_dropped {
1327             debug!(
1328                 "place_is_invalidated_at_exit({:?}) - won't be dropped",
1329                 place
1330             );
1331             return;
1332         }
1333
1334         let sd = if might_be_alive { Deep } else { Shallow(None) };
1335
1336         if places_conflict::borrow_conflicts_with_place(
1337             self.infcx.tcx,
1338             self.mir,
1339             place,
1340             borrow.kind,
1341             root_place,
1342             sd,
1343             places_conflict::PlaceConflictBias::Overlap,
1344         ) {
1345             debug!("check_for_invalidation_at_exit({:?}): INVALID", place);
1346             // FIXME: should be talking about the region lifetime instead
1347             // of just a span here.
1348             let span = self.infcx.tcx.sess.source_map().end_point(span);
1349             self.report_borrowed_value_does_not_live_long_enough(
1350                 context,
1351                 borrow,
1352                 (place, span),
1353                 None,
1354             )
1355         }
1356     }
1357
1358     /// Reports an error if this is a borrow of local data.
1359     /// This is called for all Yield statements on movable generators
1360     fn check_for_local_borrow(&mut self, borrow: &BorrowData<'tcx>, yield_span: Span) {
1361         debug!("check_for_local_borrow({:?})", borrow);
1362
1363         if borrow_of_local_data(&borrow.borrowed_place) {
1364             let err = self.infcx.tcx
1365                 .cannot_borrow_across_generator_yield(
1366                     self.retrieve_borrow_spans(borrow).var_or_use(),
1367                     yield_span,
1368                     Origin::Mir,
1369                 );
1370
1371             err.buffer(&mut self.errors_buffer);
1372         }
1373     }
1374
1375     fn check_activations(
1376         &mut self,
1377         location: Location,
1378         span: Span,
1379         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1380     ) {
1381         if !self.infcx.tcx.two_phase_borrows() {
1382             return;
1383         }
1384
1385         // Two-phase borrow support: For each activation that is newly
1386         // generated at this statement, check if it interferes with
1387         // another borrow.
1388         let borrow_set = self.borrow_set.clone();
1389         for &borrow_index in borrow_set.activations_at_location(location) {
1390             let borrow = &borrow_set[borrow_index];
1391
1392             // only mutable borrows should be 2-phase
1393             assert!(match borrow.kind {
1394                 BorrowKind::Shared | BorrowKind::Shallow => false,
1395                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
1396             });
1397
1398             self.access_place(
1399                 ContextKind::Activation.new(location),
1400                 (&borrow.borrowed_place, span),
1401                 (
1402                     Deep,
1403                     Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
1404                 ),
1405                 LocalMutationIsAllowed::No,
1406                 flow_state,
1407             );
1408             // We do not need to call `check_if_path_or_subpath_is_moved`
1409             // again, as we already called it when we made the
1410             // initial reservation.
1411         }
1412     }
1413 }
1414
1415 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
1416     fn check_if_reassignment_to_immutable_state(
1417         &mut self,
1418         context: Context,
1419         local: Local,
1420         place_span: (&Place<'tcx>, Span),
1421         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1422     ) {
1423         debug!("check_if_reassignment_to_immutable_state({:?})", local);
1424
1425         // Check if any of the initializiations of `local` have happened yet:
1426         if let Some(init_index) = self.is_local_ever_initialized(local, flow_state) {
1427             // And, if so, report an error.
1428             let init = &self.move_data.inits[init_index];
1429             let span = init.span(&self.mir);
1430             self.report_illegal_reassignment(
1431                 context, place_span, span, place_span.0
1432             );
1433         }
1434     }
1435
1436     fn check_if_full_path_is_moved(
1437         &mut self,
1438         context: Context,
1439         desired_action: InitializationRequiringAction,
1440         place_span: (&Place<'tcx>, Span),
1441         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1442     ) {
1443         let maybe_uninits = &flow_state.uninits;
1444
1445         // Bad scenarios:
1446         //
1447         // 1. Move of `a.b.c`, use of `a.b.c`
1448         // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
1449         // 3. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
1450         //    partial initialization support, one might have `a.x`
1451         //    initialized but not `a.b`.
1452         //
1453         // OK scenarios:
1454         //
1455         // 4. Move of `a.b.c`, use of `a.b.d`
1456         // 5. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1457         // 6. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1458         //    must have been initialized for the use to be sound.
1459         // 7. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1460
1461         // The dataflow tracks shallow prefixes distinctly (that is,
1462         // field-accesses on P distinctly from P itself), in order to
1463         // track substructure initialization separately from the whole
1464         // structure.
1465         //
1466         // E.g., when looking at (*a.b.c).d, if the closest prefix for
1467         // which we have a MovePath is `a.b`, then that means that the
1468         // initialization state of `a.b` is all we need to inspect to
1469         // know if `a.b.c` is valid (and from that we infer that the
1470         // dereference and `.d` access is also valid, since we assume
1471         // `a.b.c` is assigned a reference to a initialized and
1472         // well-formed record structure.)
1473
1474         // Therefore, if we seek out the *closest* prefix for which we
1475         // have a MovePath, that should capture the initialization
1476         // state for the place scenario.
1477         //
1478         // This code covers scenarios 1, 2, and 3.
1479
1480         debug!("check_if_full_path_is_moved place: {:?}", place_span.0);
1481         match self.move_path_closest_to(place_span.0) {
1482             Ok((prefix, mpi)) => {
1483                 if maybe_uninits.contains(mpi) {
1484                     self.report_use_of_moved_or_uninitialized(
1485                         context,
1486                         desired_action,
1487                         (prefix, place_span.0, place_span.1),
1488                         mpi,
1489                     );
1490                     return; // don't bother finding other problems.
1491                 }
1492             }
1493             Err(NoMovePathFound::ReachedStatic) => {
1494                 // Okay: we do not build MoveData for static variables
1495             } // Only query longest prefix with a MovePath, not further
1496               // ancestors; dataflow recurs on children when parents
1497               // move (to support partial (re)inits).
1498               //
1499               // (I.e., querying parents breaks scenario 7; but may want
1500               // to do such a query based on partial-init feature-gate.)
1501         }
1502     }
1503
1504     fn check_if_path_or_subpath_is_moved(
1505         &mut self,
1506         context: Context,
1507         desired_action: InitializationRequiringAction,
1508         place_span: (&Place<'tcx>, Span),
1509         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1510     ) {
1511         let maybe_uninits = &flow_state.uninits;
1512
1513         // Bad scenarios:
1514         //
1515         // 1. Move of `a.b.c`, use of `a` or `a.b`
1516         //    partial initialization support, one might have `a.x`
1517         //    initialized but not `a.b`.
1518         // 2. All bad scenarios from `check_if_full_path_is_moved`
1519         //
1520         // OK scenarios:
1521         //
1522         // 3. Move of `a.b.c`, use of `a.b.d`
1523         // 4. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1524         // 5. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1525         //    must have been initialized for the use to be sound.
1526         // 6. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1527
1528         self.check_if_full_path_is_moved(context, desired_action, place_span, flow_state);
1529
1530         // A move of any shallow suffix of `place` also interferes
1531         // with an attempt to use `place`. This is scenario 3 above.
1532         //
1533         // (Distinct from handling of scenarios 1+2+4 above because
1534         // `place` does not interfere with suffixes of its prefixes,
1535         // e.g., `a.b.c` does not interfere with `a.b.d`)
1536         //
1537         // This code covers scenario 1.
1538
1539         debug!("check_if_path_or_subpath_is_moved place: {:?}", place_span.0);
1540         if let Some(mpi) = self.move_path_for_place(place_span.0) {
1541             if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) {
1542                 self.report_use_of_moved_or_uninitialized(
1543                     context,
1544                     desired_action,
1545                     (place_span.0, place_span.0, place_span.1),
1546                     child_mpi,
1547                 );
1548                 return; // don't bother finding other problems.
1549             }
1550         }
1551     }
1552
1553     /// Currently MoveData does not store entries for all places in
1554     /// the input MIR. For example it will currently filter out
1555     /// places that are Copy; thus we do not track places of shared
1556     /// reference type. This routine will walk up a place along its
1557     /// prefixes, searching for a foundational place that *is*
1558     /// tracked in the MoveData.
1559     ///
1560     /// An Err result includes a tag indicated why the search failed.
1561     /// Currently this can only occur if the place is built off of a
1562     /// static variable, as we do not track those in the MoveData.
1563     fn move_path_closest_to<'a>(
1564         &mut self,
1565         place: &'a Place<'tcx>,
1566     ) -> Result<(&'a Place<'tcx>, MovePathIndex), NoMovePathFound> where 'cx: 'a {
1567         let mut last_prefix = place;
1568         for prefix in self.prefixes(place, PrefixSet::All) {
1569             if let Some(mpi) = self.move_path_for_place(prefix) {
1570                 return Ok((prefix, mpi));
1571             }
1572             last_prefix = prefix;
1573         }
1574         match *last_prefix {
1575             Place::Base(PlaceBase::Local(_)) => panic!("should have move path for every Local"),
1576             Place::Projection(_) => panic!("PrefixSet::All meant don't stop for Projection"),
1577             Place::Base(PlaceBase::Static(_)) => Err(NoMovePathFound::ReachedStatic),
1578         }
1579     }
1580
1581     fn move_path_for_place(&mut self, place: &Place<'tcx>) -> Option<MovePathIndex> {
1582         // If returns None, then there is no move path corresponding
1583         // to a direct owner of `place` (which means there is nothing
1584         // that borrowck tracks for its analysis).
1585
1586         match self.move_data.rev_lookup.find(place) {
1587             LookupResult::Parent(_) => None,
1588             LookupResult::Exact(mpi) => Some(mpi),
1589         }
1590     }
1591
1592     fn check_if_assigned_path_is_moved(
1593         &mut self,
1594         context: Context,
1595         (place, span): (&Place<'tcx>, Span),
1596         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1597     ) {
1598         debug!("check_if_assigned_path_is_moved place: {:?}", place);
1599         // recur down place; dispatch to external checks when necessary
1600         let mut place = place;
1601         loop {
1602             match *place {
1603                 Place::Base(PlaceBase::Local(_)) | Place::Base(PlaceBase::Static(_)) => {
1604                     // assigning to `x` does not require `x` be initialized.
1605                     break;
1606                 }
1607                 Place::Projection(ref proj) => {
1608                     let Projection { ref base, ref elem } = **proj;
1609                     match *elem {
1610                         ProjectionElem::Index(_/*operand*/) |
1611                         ProjectionElem::ConstantIndex { .. } |
1612                         // assigning to P[i] requires P to be valid.
1613                         ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
1614                         // assigning to (P->variant) is okay if assigning to `P` is okay
1615                         //
1616                         // FIXME: is this true even if P is a adt with a dtor?
1617                         { }
1618
1619                         // assigning to (*P) requires P to be initialized
1620                         ProjectionElem::Deref => {
1621                             self.check_if_full_path_is_moved(
1622                                 context, InitializationRequiringAction::Use,
1623                                 (base, span), flow_state);
1624                             // (base initialized; no need to
1625                             // recur further)
1626                             break;
1627                         }
1628
1629                         ProjectionElem::Subslice { .. } => {
1630                             panic!("we don't allow assignments to subslices, context: {:?}",
1631                                    context);
1632                         }
1633
1634                         ProjectionElem::Field(..) => {
1635                             // if type of `P` has a dtor, then
1636                             // assigning to `P.f` requires `P` itself
1637                             // be already initialized
1638                             let tcx = self.infcx.tcx;
1639                             match base.ty(self.mir, tcx).ty.sty {
1640                                 ty::Adt(def, _) if def.has_dtor(tcx) => {
1641                                     self.check_if_path_or_subpath_is_moved(
1642                                         context, InitializationRequiringAction::Assignment,
1643                                         (base, span), flow_state);
1644
1645                                     // (base initialized; no need to
1646                                     // recur further)
1647                                     break;
1648                                 }
1649
1650
1651                                 // Once `let s; s.x = V; read(s.x);`,
1652                                 // is allowed, remove this match arm.
1653                                 ty::Adt(..) | ty::Tuple(..) => {
1654                                     check_parent_of_field(self, context, base, span, flow_state);
1655
1656                                     if let Some(local) = place.base_local() {
1657                                         // rust-lang/rust#21232,
1658                                         // #54499, #54986: during
1659                                         // period where we reject
1660                                         // partial initialization, do
1661                                         // not complain about
1662                                         // unnecessary `mut` on an
1663                                         // attempt to do a partial
1664                                         // initialization.
1665                                         self.used_mut.insert(local);
1666                                     }
1667                                 }
1668
1669                                 _ => {}
1670                             }
1671                         }
1672                     }
1673
1674                     place = base;
1675                     continue;
1676                 }
1677             }
1678         }
1679
1680         fn check_parent_of_field<'cx, 'gcx, 'tcx>(
1681             this: &mut MirBorrowckCtxt<'cx, 'gcx, 'tcx>,
1682             context: Context,
1683             base: &Place<'tcx>,
1684             span: Span,
1685             flow_state: &Flows<'cx, 'gcx, 'tcx>,
1686         ) {
1687             // rust-lang/rust#21232: Until Rust allows reads from the
1688             // initialized parts of partially initialized structs, we
1689             // will, starting with the 2018 edition, reject attempts
1690             // to write to structs that are not fully initialized.
1691             //
1692             // In other words, *until* we allow this:
1693             //
1694             // 1. `let mut s; s.x = Val; read(s.x);`
1695             //
1696             // we will for now disallow this:
1697             //
1698             // 2. `let mut s; s.x = Val;`
1699             //
1700             // and also this:
1701             //
1702             // 3. `let mut s = ...; drop(s); s.x=Val;`
1703             //
1704             // This does not use check_if_path_or_subpath_is_moved,
1705             // because we want to *allow* reinitializations of fields:
1706             // e.g., want to allow
1707             //
1708             // `let mut s = ...; drop(s.x); s.x=Val;`
1709             //
1710             // This does not use check_if_full_path_is_moved on
1711             // `base`, because that would report an error about the
1712             // `base` as a whole, but in this scenario we *really*
1713             // want to report an error about the actual thing that was
1714             // moved, which may be some prefix of `base`.
1715
1716             // Shallow so that we'll stop at any dereference; we'll
1717             // report errors about issues with such bases elsewhere.
1718             let maybe_uninits = &flow_state.uninits;
1719
1720             // Find the shortest uninitialized prefix you can reach
1721             // without going over a Deref.
1722             let mut shortest_uninit_seen = None;
1723             for prefix in this.prefixes(base, PrefixSet::Shallow) {
1724                 let mpi = match this.move_path_for_place(prefix) {
1725                     Some(mpi) => mpi, None => continue,
1726                 };
1727
1728                 if maybe_uninits.contains(mpi) {
1729                     debug!("check_parent_of_field updating shortest_uninit_seen from {:?} to {:?}",
1730                            shortest_uninit_seen, Some((prefix, mpi)));
1731                     shortest_uninit_seen = Some((prefix, mpi));
1732                 } else {
1733                     debug!("check_parent_of_field {:?} is definitely initialized", (prefix, mpi));
1734                 }
1735             }
1736
1737             if let Some((prefix, mpi)) = shortest_uninit_seen {
1738                 // Check for a reassignment into a uninitialized field of a union (for example,
1739                 // after a move out). In this case, do not report a error here. There is an
1740                 // exception, if this is the first assignment into the union (that is, there is
1741                 // no move out from an earlier location) then this is an attempt at initialization
1742                 // of the union - we should error in that case.
1743                 let tcx = this.infcx.tcx;
1744                 if let ty::Adt(def, _) = base.ty(this.mir, tcx).ty.sty {
1745                     if def.is_union() {
1746                         if this.move_data.path_map[mpi].iter().any(|moi| {
1747                             this.move_data.moves[*moi].source.is_predecessor_of(
1748                                 context.loc, this.mir,
1749                             )
1750                         }) {
1751                             return;
1752                         }
1753                     }
1754                 }
1755
1756                 this.report_use_of_moved_or_uninitialized(
1757                     context,
1758                     InitializationRequiringAction::PartialAssignment,
1759                     (prefix, base, span),
1760                     mpi,
1761                 );
1762             }
1763         }
1764     }
1765
1766     /// Checks the permissions for the given place and read or write kind
1767     ///
1768     /// Returns `true` if an error is reported.
1769     fn check_access_permissions(
1770         &mut self,
1771         (place, span): (&Place<'tcx>, Span),
1772         kind: ReadOrWrite,
1773         is_local_mutation_allowed: LocalMutationIsAllowed,
1774         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1775         location: Location,
1776     ) -> bool {
1777         debug!(
1778             "check_access_permissions({:?}, {:?}, is_local_mutation_allowed: {:?})",
1779             place, kind, is_local_mutation_allowed
1780         );
1781
1782         let error_access;
1783         let the_place_err;
1784
1785         // rust-lang/rust#21232, #54986: during period where we reject
1786         // partial initialization, do not complain about mutability
1787         // errors except for actual mutation (as opposed to an attempt
1788         // to do a partial initialization).
1789         let previously_initialized = if let Some(local) = place.base_local() {
1790             self.is_local_ever_initialized(local, flow_state).is_some()
1791         } else {
1792             true
1793         };
1794
1795         match kind {
1796             Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1797             | Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. }))
1798             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1799             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. })) => {
1800                 let is_local_mutation_allowed = match borrow_kind {
1801                     BorrowKind::Unique => LocalMutationIsAllowed::Yes,
1802                     BorrowKind::Mut { .. } => is_local_mutation_allowed,
1803                     BorrowKind::Shared | BorrowKind::Shallow => unreachable!(),
1804                 };
1805                 match self.is_mutable(place, is_local_mutation_allowed) {
1806                     Ok(root_place) => {
1807                         self.add_used_mut(root_place, flow_state);
1808                         return false;
1809                     }
1810                     Err(place_err) => {
1811                         error_access = AccessKind::MutableBorrow;
1812                         the_place_err = place_err;
1813                     }
1814                 }
1815             }
1816             Reservation(WriteKind::Mutate) | Write(WriteKind::Mutate) => {
1817                 match self.is_mutable(place, is_local_mutation_allowed) {
1818                     Ok(root_place) => {
1819                         self.add_used_mut(root_place, flow_state);
1820                         return false;
1821                     }
1822                     Err(place_err) => {
1823                         error_access = AccessKind::Mutate;
1824                         the_place_err = place_err;
1825                     }
1826                 }
1827             }
1828
1829             Reservation(wk @ WriteKind::Move)
1830             | Write(wk @ WriteKind::Move)
1831             | Reservation(wk @ WriteKind::StorageDeadOrDrop)
1832             | Reservation(wk @ WriteKind::MutableBorrow(BorrowKind::Shared))
1833             | Reservation(wk @ WriteKind::MutableBorrow(BorrowKind::Shallow))
1834             | Write(wk @ WriteKind::StorageDeadOrDrop)
1835             | Write(wk @ WriteKind::MutableBorrow(BorrowKind::Shared))
1836             | Write(wk @ WriteKind::MutableBorrow(BorrowKind::Shallow)) => {
1837                 if let (Err(_place_err), true) = (
1838                     self.is_mutable(place, is_local_mutation_allowed),
1839                     self.errors_buffer.is_empty()
1840                 ) {
1841                     if self.infcx.tcx.migrate_borrowck() {
1842                         // rust-lang/rust#46908: In pure NLL mode this
1843                         // code path should be unreachable (and thus
1844                         // we signal an ICE in the else branch
1845                         // here). But we can legitimately get here
1846                         // under borrowck=migrate mode, so instead of
1847                         // ICE'ing we instead report a legitimate
1848                         // error (which will then be downgraded to a
1849                         // warning by the migrate machinery).
1850                         error_access = match wk {
1851                             WriteKind::MutableBorrow(_) => AccessKind::MutableBorrow,
1852                             WriteKind::Move => AccessKind::Move,
1853                             WriteKind::StorageDeadOrDrop |
1854                             WriteKind::Mutate => AccessKind::Mutate,
1855                         };
1856                         self.report_mutability_error(
1857                             place,
1858                             span,
1859                             _place_err,
1860                             error_access,
1861                             location,
1862                         );
1863                     } else {
1864                         span_bug!(
1865                             span,
1866                             "Accessing `{:?}` with the kind `{:?}` shouldn't be possible",
1867                             place,
1868                             kind,
1869                         );
1870                     }
1871                 }
1872                 return false;
1873             }
1874             Activation(..) => {
1875                 // permission checks are done at Reservation point.
1876                 return false;
1877             }
1878             Read(ReadKind::Borrow(BorrowKind::Unique))
1879             | Read(ReadKind::Borrow(BorrowKind::Mut { .. }))
1880             | Read(ReadKind::Borrow(BorrowKind::Shared))
1881             | Read(ReadKind::Borrow(BorrowKind::Shallow))
1882             | Read(ReadKind::Copy) => {
1883                 // Access authorized
1884                 return false;
1885             }
1886         }
1887
1888         // at this point, we have set up the error reporting state.
1889         return if previously_initialized {
1890             self.report_mutability_error(
1891                 place,
1892                 span,
1893                 the_place_err,
1894                 error_access,
1895                 location,
1896             );
1897             true
1898         } else {
1899             false
1900         };
1901     }
1902
1903     fn is_local_ever_initialized(&self,
1904                                  local: Local,
1905                                  flow_state: &Flows<'cx, 'gcx, 'tcx>)
1906                                  -> Option<InitIndex>
1907     {
1908         let mpi = self.move_data.rev_lookup.find_local(local);
1909         let ii = &self.move_data.init_path_map[mpi];
1910         for &index in ii {
1911             if flow_state.ever_inits.contains(index) {
1912                 return Some(index);
1913             }
1914         }
1915         None
1916     }
1917
1918     /// Adds the place into the used mutable variables set
1919     fn add_used_mut<'d>(
1920         &mut self,
1921         root_place: RootPlace<'d, 'tcx>,
1922         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1923     ) {
1924         match root_place {
1925             RootPlace {
1926                 place: Place::Base(PlaceBase::Local(local)),
1927                 is_local_mutation_allowed,
1928             } => {
1929                 // If the local may have been initialized, and it is now currently being
1930                 // mutated, then it is justified to be annotated with the `mut`
1931                 // keyword, since the mutation may be a possible reassignment.
1932                 if is_local_mutation_allowed != LocalMutationIsAllowed::Yes &&
1933                     self.is_local_ever_initialized(*local, flow_state).is_some()
1934                 {
1935                     self.used_mut.insert(*local);
1936                 }
1937             }
1938             RootPlace {
1939                 place: _,
1940                 is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1941             } => {}
1942             RootPlace {
1943                 place: place @ Place::Projection(_),
1944                 is_local_mutation_allowed: _,
1945             } => {
1946                 if let Some(field) = place.is_upvar_field_projection(self.mir, &self.infcx.tcx) {
1947                     self.used_mut_upvars.push(field);
1948                 }
1949             }
1950             RootPlace {
1951                 place: Place::Base(PlaceBase::Static(..)),
1952                 is_local_mutation_allowed: _,
1953             } => {}
1954         }
1955     }
1956
1957     /// Whether this value can be written or borrowed mutably.
1958     /// Returns the root place if the place passed in is a projection.
1959     fn is_mutable<'d>(
1960         &self,
1961         place: &'d Place<'tcx>,
1962         is_local_mutation_allowed: LocalMutationIsAllowed,
1963     ) -> Result<RootPlace<'d, 'tcx>, &'d Place<'tcx>> {
1964         match *place {
1965             Place::Base(PlaceBase::Local(local)) => {
1966                 let local = &self.mir.local_decls[local];
1967                 match local.mutability {
1968                     Mutability::Not => match is_local_mutation_allowed {
1969                         LocalMutationIsAllowed::Yes => Ok(RootPlace {
1970                             place,
1971                             is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1972                         }),
1973                         LocalMutationIsAllowed::ExceptUpvars => Ok(RootPlace {
1974                             place,
1975                             is_local_mutation_allowed: LocalMutationIsAllowed::ExceptUpvars,
1976                         }),
1977                         LocalMutationIsAllowed::No => Err(place),
1978                     },
1979                     Mutability::Mut => Ok(RootPlace {
1980                         place,
1981                         is_local_mutation_allowed,
1982                     }),
1983                 }
1984             }
1985             // The rules for promotion are made by `qualify_consts`, there wouldn't even be a
1986             // `Place::Promoted` if the promotion weren't 100% legal. So we just forward this
1987             Place::Base(PlaceBase::Static(box Static{kind: StaticKind::Promoted(_), ..})) =>
1988                 Ok(RootPlace {
1989                     place,
1990                     is_local_mutation_allowed,
1991                 }),
1992             Place::Base(PlaceBase::Static(box Static{ kind: StaticKind::Static(def_id), .. })) => {
1993                 if self.infcx.tcx.is_static(def_id) != Some(hir::Mutability::MutMutable) {
1994                     Err(place)
1995                 } else {
1996                     Ok(RootPlace {
1997                         place,
1998                         is_local_mutation_allowed,
1999                     })
2000                 }
2001             }
2002             Place::Projection(ref proj) => {
2003                 match proj.elem {
2004                     ProjectionElem::Deref => {
2005                         let base_ty = proj.base.ty(self.mir, self.infcx.tcx).ty;
2006
2007                         // Check the kind of deref to decide
2008                         match base_ty.sty {
2009                             ty::Ref(_, _, mutbl) => {
2010                                 match mutbl {
2011                                     // Shared borrowed data is never mutable
2012                                     hir::MutImmutable => Err(place),
2013                                     // Mutably borrowed data is mutable, but only if we have a
2014                                     // unique path to the `&mut`
2015                                     hir::MutMutable => {
2016                                         let mode = match place.is_upvar_field_projection(
2017                                             self.mir, &self.infcx.tcx)
2018                                         {
2019                                             Some(field)
2020                                                 if {
2021                                                     self.mir.upvar_decls[field.index()].by_ref
2022                                                 } =>
2023                                             {
2024                                                 is_local_mutation_allowed
2025                                             }
2026                                             _ => LocalMutationIsAllowed::Yes,
2027                                         };
2028
2029                                         self.is_mutable(&proj.base, mode)
2030                                     }
2031                                 }
2032                             }
2033                             ty::RawPtr(tnm) => {
2034                                 match tnm.mutbl {
2035                                     // `*const` raw pointers are not mutable
2036                                     hir::MutImmutable => Err(place),
2037                                     // `*mut` raw pointers are always mutable, regardless of
2038                                     // context. The users have to check by themselves.
2039                                     hir::MutMutable => {
2040                                         Ok(RootPlace {
2041                                             place,
2042                                             is_local_mutation_allowed,
2043                                         })
2044                                     }
2045                                 }
2046                             }
2047                             // `Box<T>` owns its content, so mutable if its location is mutable
2048                             _ if base_ty.is_box() => {
2049                                 self.is_mutable(&proj.base, is_local_mutation_allowed)
2050                             }
2051                             // Deref should only be for reference, pointers or boxes
2052                             _ => bug!("Deref of unexpected type: {:?}", base_ty),
2053                         }
2054                     }
2055                     // All other projections are owned by their base path, so mutable if
2056                     // base path is mutable
2057                     ProjectionElem::Field(..)
2058                     | ProjectionElem::Index(..)
2059                     | ProjectionElem::ConstantIndex { .. }
2060                     | ProjectionElem::Subslice { .. }
2061                     | ProjectionElem::Downcast(..) => {
2062                         let upvar_field_projection = place.is_upvar_field_projection(
2063                             self.mir, &self.infcx.tcx);
2064                         if let Some(field) = upvar_field_projection {
2065                             let decl = &self.mir.upvar_decls[field.index()];
2066                             debug!(
2067                                 "decl.mutability={:?} local_mutation_is_allowed={:?} place={:?}",
2068                                 decl, is_local_mutation_allowed, place
2069                             );
2070                             match (decl.mutability, is_local_mutation_allowed) {
2071                                 (Mutability::Not, LocalMutationIsAllowed::No)
2072                                 | (Mutability::Not, LocalMutationIsAllowed::ExceptUpvars) => {
2073                                     Err(place)
2074                                 }
2075                                 (Mutability::Not, LocalMutationIsAllowed::Yes)
2076                                 | (Mutability::Mut, _) => {
2077                                     // Subtle: this is an upvar
2078                                     // reference, so it looks like
2079                                     // `self.foo` -- we want to double
2080                                     // check that the context `*self`
2081                                     // is mutable (i.e., this is not a
2082                                     // `Fn` closure).  But if that
2083                                     // check succeeds, we want to
2084                                     // *blame* the mutability on
2085                                     // `place` (that is,
2086                                     // `self.foo`). This is used to
2087                                     // propagate the info about
2088                                     // whether mutability declarations
2089                                     // are used outwards, so that we register
2090                                     // the outer variable as mutable. Otherwise a
2091                                     // test like this fails to record the `mut`
2092                                     // as needed:
2093                                     //
2094                                     // ```
2095                                     // fn foo<F: FnOnce()>(_f: F) { }
2096                                     // fn main() {
2097                                     //     let var = Vec::new();
2098                                     //     foo(move || {
2099                                     //         var.push(1);
2100                                     //     });
2101                                     // }
2102                                     // ```
2103                                     let _ = self.is_mutable(&proj.base, is_local_mutation_allowed)?;
2104                                     Ok(RootPlace {
2105                                         place,
2106                                         is_local_mutation_allowed,
2107                                     })
2108                                 }
2109                             }
2110                         } else {
2111                             self.is_mutable(&proj.base, is_local_mutation_allowed)
2112                         }
2113                     }
2114                 }
2115             }
2116         }
2117     }
2118 }
2119
2120 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2121 enum NoMovePathFound {
2122     ReachedStatic,
2123 }
2124
2125 /// The degree of overlap between 2 places for borrow-checking.
2126 enum Overlap {
2127     /// The places might partially overlap - in this case, we give
2128     /// up and say that they might conflict. This occurs when
2129     /// different fields of a union are borrowed. For example,
2130     /// if `u` is a union, we have no way of telling how disjoint
2131     /// `u.a.x` and `a.b.y` are.
2132     Arbitrary,
2133     /// The places have the same type, and are either completely disjoint
2134     /// or equal - i.e., they can't "partially" overlap as can occur with
2135     /// unions. This is the "base case" on which we recur for extensions
2136     /// of the place.
2137     EqualOrDisjoint,
2138     /// The places are disjoint, so we know all extensions of them
2139     /// will also be disjoint.
2140     Disjoint,
2141 }
2142
2143 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2144 struct Context {
2145     kind: ContextKind,
2146     loc: Location,
2147 }
2148
2149 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2150 enum ContextKind {
2151     Activation,
2152     AssignLhs,
2153     AssignRhs,
2154     SetDiscrim,
2155     InlineAsm,
2156     SwitchInt,
2157     Drop,
2158     DropAndReplace,
2159     CallOperator,
2160     CallOperand,
2161     CallDest,
2162     Assert,
2163     Yield,
2164     FakeRead,
2165     StorageDead,
2166 }
2167
2168 impl ContextKind {
2169     fn new(self, loc: Location) -> Context {
2170         Context {
2171             kind: self,
2172             loc,
2173         }
2174     }
2175 }