src/librustc_mir/borrow_check/mod.rs

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