src/librustc_mir/borrow_check/mod.rs

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