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