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