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