src/librustc_mir/borrow_check/mod.rs

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