src/librustc_mir/borrow_check/mod.rs

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