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::{AggregateKind, BasicBlock, BorrowCheckResult, BorrowKind};
  20 use rustc::mir::{ClearCrossCrate, Local, Location, Mir, Mutability, Operand, Place};
  21 use rustc::mir::{Field, Projection, ProjectionElem, Rvalue, Statement, StatementKind};
  22 use rustc::mir::{Terminator, TerminatorKind};
  23 use rustc::ty::query::Providers;
  24 use rustc::ty::{self, ParamEnv, TyCtxt};
  25
  26 use rustc_data_structures::graph::dominators::Dominators;
  27 use rustc_data_structures::fx::FxHashSet;
  28 use rustc_data_structures::indexed_set::IdxSetBuf;
  29 use rustc_data_structures::indexed_vec::Idx;
  30 use rustc_data_structures::small_vec::SmallVec;
  31
  32 use std::rc::Rc;
  33
  34 use syntax_pos::Span;
  35
  36 use dataflow::indexes::BorrowIndex;
  37 use dataflow::move_paths::{HasMoveData, LookupResult, MoveData, MoveError, MovePathIndex};
  38 use dataflow::Borrows;
  39 use dataflow::DataflowResultsConsumer;
  40 use dataflow::FlowAtLocation;
  41 use dataflow::MoveDataParamEnv;
  42 use dataflow::{do_dataflow, DebugFormatted};
  43 use dataflow::{EverInitializedPlaces, MovingOutStatements};
  44 use dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
  45 use util::borrowck_errors::{BorrowckErrors, Origin};
  46
  47 use self::borrow_set::{BorrowData, BorrowSet};
  48 use self::flows::Flows;
  49 use self::location::LocationTable;
  50 use self::prefixes::PrefixSet;
  51 use self::MutateMode::{JustWrite, WriteAndRead};
  52 use self::mutability_errors::AccessKind;
  53
  54 use self::path_utils::*;
  55
  56 crate mod borrow_set;
  57 mod error_reporting;
  58 mod flows;
  59 mod location;
  60 mod move_errors;
  61 mod mutability_errors;
  62 mod path_utils;
  63 crate mod place_ext;
  64 mod places_conflict;
  65 mod prefixes;
  66 mod used_muts;
  67
  68 pub(crate) mod nll;
  69
  70 pub fn provide(providers: &mut Providers) {
  71     *providers = Providers {
  72         mir_borrowck,
  73         ..*providers
  74     };
  75 }
  76
  77 fn mir_borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> BorrowCheckResult<'tcx> {
  78     let input_mir = tcx.mir_validated(def_id);
  79     debug!("run query mir_borrowck: {}", tcx.item_path_str(def_id));
  80
  81     let mut return_early;
  82
  83     // Return early if we are not supposed to use MIR borrow checker for this function.
  84     return_early = !tcx.has_attr(def_id, "rustc_mir") && !tcx.use_mir_borrowck();
  85
  86     if tcx.is_struct_constructor(def_id) {
  87         // We are not borrow checking the automatically generated struct constructors
  88         // because we want to accept structs such as this (taken from the `linked-hash-map`
  89         // crate):
  90         // ```rust
  91         // struct Qey<Q: ?Sized>(Q);
  92         // ```
  93         // MIR of this struct constructor looks something like this:
  94         // ```rust
  95         // fn Qey(_1: Q) -> Qey<Q>{
  96         //     let mut _0: Qey<Q>;                  // return place
  97         //
  98         //     bb0: {
  99         //         (_0.0: Q) = move _1;             // bb0[0]: scope 0 at src/main.rs:1:1: 1:26
 100         //         return;                          // bb0[1]: scope 0 at src/main.rs:1:1: 1:26
 101         //     }
 102         // }
 103         // ```
 104         // The problem here is that `(_0.0: Q) = move _1;` is valid only if `Q` is
 105         // of statically known size, which is not known to be true because of the
 106         // `Q: ?Sized` constraint. However, it is true because the constructor can be
 107         // called only when `Q` is of statically known size.
 108         return_early = true;
 109     }
 110
 111     if return_early {
 112         return BorrowCheckResult {
 113             closure_requirements: None,
 114             used_mut_upvars: SmallVec::new(),
 115         };
 116     }
 117
 118     let opt_closure_req = tcx.infer_ctxt().enter(|infcx| {
 119         let input_mir: &Mir = &input_mir.borrow();
 120         do_mir_borrowck(&infcx, input_mir, def_id)
 121     });
 122     debug!("mir_borrowck done");
 123
 124     opt_closure_req
 125 }
 126
 127 fn do_mir_borrowck<'a, 'gcx, 'tcx>(
 128     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 129     input_mir: &Mir<'gcx>,
 130     def_id: DefId,
 131 ) -> BorrowCheckResult<'gcx> {
 132     debug!("do_mir_borrowck(def_id = {:?})", def_id);
 133
 134     let tcx = infcx.tcx;
 135     let attributes = tcx.get_attrs(def_id);
 136     let param_env = tcx.param_env(def_id);
 137     let id = tcx
 138         .hir
 139         .as_local_node_id(def_id)
 140         .expect("do_mir_borrowck: non-local DefId");
 141
 142     // Replace all regions with fresh inference variables. This
 143     // requires first making our own copy of the MIR. This copy will
 144     // be modified (in place) to contain non-lexical lifetimes. It
 145     // will have a lifetime tied to the inference context.
 146     let mut mir: Mir<'tcx> = input_mir.clone();
 147     let free_regions = nll::replace_regions_in_mir(infcx, def_id, param_env, &mut mir);
 148     let mir = &mir; // no further changes
 149     let location_table = &LocationTable::new(mir);
 150
 151     let (move_data, move_errors): (MoveData<'tcx>, Option<Vec<MoveError<'tcx>>>) =
 152         match MoveData::gather_moves(mir, tcx) {
 153             Ok(move_data) => (move_data, None),
 154             Err((move_data, move_errors)) => (move_data, Some(move_errors)),
 155         };
 156
 157     let mdpe = MoveDataParamEnv {
 158         move_data: move_data,
 159         param_env: param_env,
 160     };
 161     let body_id = match tcx.def_key(def_id).disambiguated_data.data {
 162         DefPathData::StructCtor | DefPathData::EnumVariant(_) => None,
 163         _ => Some(tcx.hir.body_owned_by(id)),
 164     };
 165
 166     let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
 167     let mut flow_inits = FlowAtLocation::new(do_dataflow(
 168         tcx,
 169         mir,
 170         id,
 171         &attributes,
 172         &dead_unwinds,
 173         MaybeInitializedPlaces::new(tcx, mir, &mdpe),
 174         |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
 175     ));
 176     let flow_uninits = FlowAtLocation::new(do_dataflow(
 177         tcx,
 178         mir,
 179         id,
 180         &attributes,
 181         &dead_unwinds,
 182         MaybeUninitializedPlaces::new(tcx, mir, &mdpe),
 183         |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
 184     ));
 185     let flow_move_outs = FlowAtLocation::new(do_dataflow(
 186         tcx,
 187         mir,
 188         id,
 189         &attributes,
 190         &dead_unwinds,
 191         MovingOutStatements::new(tcx, mir, &mdpe),
 192         |bd, i| DebugFormatted::new(&bd.move_data().moves[i]),
 193     ));
 194     let flow_ever_inits = FlowAtLocation::new(do_dataflow(
 195         tcx,
 196         mir,
 197         id,
 198         &attributes,
 199         &dead_unwinds,
 200         EverInitializedPlaces::new(tcx, mir, &mdpe),
 201         |bd, i| DebugFormatted::new(&bd.move_data().inits[i]),
 202     ));
 203
 204     let borrow_set = Rc::new(BorrowSet::build(tcx, mir));
 205
 206     // If we are in non-lexical mode, compute the non-lexical lifetimes.
 207     let (regioncx, polonius_output, opt_closure_req) = nll::compute_regions(
 208         infcx,
 209         def_id,
 210         free_regions,
 211         mir,
 212         location_table,
 213         param_env,
 214         &mut flow_inits,
 215         &mdpe.move_data,
 216         &borrow_set,
 217     );
 218     let regioncx = Rc::new(regioncx);
 219     let flow_inits = flow_inits; // remove mut
 220
 221     let flow_borrows = FlowAtLocation::new(do_dataflow(
 222         tcx,
 223         mir,
 224         id,
 225         &attributes,
 226         &dead_unwinds,
 227         Borrows::new(tcx, mir, regioncx.clone(), def_id, body_id, &borrow_set),
 228         |rs, i| DebugFormatted::new(&rs.location(i)),
 229     ));
 230
 231     let movable_generator = match tcx.hir.get(id) {
 232         hir::map::Node::NodeExpr(&hir::Expr {
 233             node: hir::ExprKind::Closure(.., Some(hir::GeneratorMovability::Static)),
 234             ..
 235         }) => false,
 236         _ => true,
 237     };
 238
 239     let dominators = mir.dominators();
 240
 241     let mut mbcx = MirBorrowckCtxt {
 242         tcx: tcx,
 243         mir: mir,
 244         mir_def_id: def_id,
 245         move_data: &mdpe.move_data,
 246         param_env: param_env,
 247         location_table,
 248         movable_generator,
 249         locals_are_invalidated_at_exit: match tcx.hir.body_owner_kind(id) {
 250             hir::BodyOwnerKind::Const | hir::BodyOwnerKind::Static(_) => false,
 251             hir::BodyOwnerKind::Fn => true,
 252         },
 253         access_place_error_reported: FxHashSet(),
 254         reservation_error_reported: FxHashSet(),
 255         moved_error_reported: FxHashSet(),
 256         nonlexical_regioncx: regioncx,
 257         used_mut: FxHashSet(),
 258         used_mut_upvars: SmallVec::new(),
 259         borrow_set,
 260         dominators,
 261     };
 262
 263     let mut state = Flows::new(
 264         flow_borrows,
 265         flow_inits,
 266         flow_uninits,
 267         flow_move_outs,
 268         flow_ever_inits,
 269         polonius_output,
 270     );
 271
 272     if let Some(errors) = move_errors {
 273         mbcx.report_move_errors(errors);
 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(
 927                 place_span,
 928                 rw,
 929                 is_local_mutation_allowed,
 930                 flow_state,
 931                 context.loc,
 932             );
 933         let conflict_error =
 934             self.check_access_for_conflict(context, place_span, sd, rw, flow_state);
 935
 936         if conflict_error || mutability_error {
 937             debug!(
 938                 "access_place: logging error place_span=`{:?}` kind=`{:?}`",
 939                 place_span, kind
 940             );
 941             self.access_place_error_reported
 942                 .insert((place_span.0.clone(), place_span.1));
 943         }
 944
 945         AccessErrorsReported {
 946             mutability_error,
 947             conflict_error,
 948         }
 949     }
 950
 951     fn check_access_for_conflict(
 952         &mut self,
 953         context: Context,
 954         place_span: (&Place<'tcx>, Span),
 955         sd: ShallowOrDeep,
 956         rw: ReadOrWrite,
 957         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 958     ) -> bool {
 959         debug!(
 960             "check_access_for_conflict(context={:?}, place_span={:?}, sd={:?}, rw={:?})",
 961             context, place_span, sd, rw,
 962         );
 963
 964         let mut error_reported = false;
 965         let tcx = self.tcx;
 966         let mir = self.mir;
 967         let location = self.location_table.start_index(context.loc);
 968         let borrow_set = self.borrow_set.clone();
 969         each_borrow_involving_path(
 970             self,
 971             tcx,
 972             mir,
 973             context,
 974             (sd, place_span.0),
 975             &borrow_set,
 976             flow_state.borrows_in_scope(location),
 977             |this, borrow_index, borrow| match (rw, borrow.kind) {
 978                 // Obviously an activation is compatible with its own
 979                 // reservation (or even prior activating uses of same
 980                 // borrow); so don't check if they interfere.
 981                 //
 982                 // NOTE: *reservations* do conflict with themselves;
 983                 // thus aren't injecting unsoundenss w/ this check.)
 984                 (Activation(_, activating), _) if activating == borrow_index => {
 985                     debug!(
 986                         "check_access_for_conflict place_span: {:?} sd: {:?} rw: {:?} \
 987                          skipping {:?} b/c activation of same borrow_index",
 988                         place_span,
 989                         sd,
 990                         rw,
 991                         (borrow_index, borrow),
 992                     );
 993                     Control::Continue
 994                 }
 995
 996                 (Read(_), BorrowKind::Shared) | (Reservation(..), BorrowKind::Shared) => {
 997                     Control::Continue
 998                 }
 999
1000                 (Read(kind), BorrowKind::Unique) | (Read(kind), BorrowKind::Mut { .. }) => {
1001                     // Reading from mere reservations of mutable-borrows is OK.
1002                     if !is_active(&this.dominators, borrow, context.loc) {
1003                         assert!(allow_two_phase_borrow(&this.tcx, borrow.kind));
1004                         return Control::Continue;
1005                     }
1006
1007                     match kind {
1008                         ReadKind::Copy => {
1009                             error_reported = true;
1010                             this.report_use_while_mutably_borrowed(context, place_span, borrow)
1011                         }
1012                         ReadKind::Borrow(bk) => {
1013                             error_reported = true;
1014                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1015                         }
1016                     }
1017                     Control::Break
1018                 }
1019
1020                 (Reservation(kind), BorrowKind::Unique)
1021                 | (Reservation(kind), BorrowKind::Mut { .. })
1022                 | (Activation(kind, _), _)
1023                 | (Write(kind), _) => {
1024                     match rw {
1025                         Reservation(_) => {
1026                             debug!(
1027                                 "recording invalid reservation of \
1028                                  place: {:?}",
1029                                 place_span.0
1030                             );
1031                             this.reservation_error_reported.insert(place_span.0.clone());
1032                         }
1033                         Activation(_, activating) => {
1034                             debug!(
1035                                 "observing check_place for activation of \
1036                                  borrow_index: {:?}",
1037                                 activating
1038                             );
1039                         }
1040                         Read(..) | Write(..) => {}
1041                     }
1042
1043                     match kind {
1044                         WriteKind::MutableBorrow(bk) => {
1045                             error_reported = true;
1046                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1047                         }
1048                         WriteKind::StorageDeadOrDrop => {
1049                             error_reported = true;
1050                             this.report_borrowed_value_does_not_live_long_enough(
1051                                 context,
1052                                 borrow,
1053                                 place_span,
1054                                 Some(kind),
1055                             );
1056                         }
1057                         WriteKind::Mutate => {
1058                             error_reported = true;
1059                             this.report_illegal_mutation_of_borrowed(context, place_span, borrow)
1060                         }
1061                         WriteKind::Move => {
1062                             error_reported = true;
1063                             this.report_move_out_while_borrowed(context, place_span, &borrow)
1064                         }
1065                     }
1066                     Control::Break
1067                 }
1068             },
1069         );
1070
1071         error_reported
1072     }
1073
1074     fn mutate_place(
1075         &mut self,
1076         context: Context,
1077         place_span: (&Place<'tcx>, Span),
1078         kind: ShallowOrDeep,
1079         mode: MutateMode,
1080         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1081     ) {
1082         // Write of P[i] or *P, or WriteAndRead of any P, requires P init'd.
1083         match mode {
1084             MutateMode::WriteAndRead => {
1085                 self.check_if_path_or_subpath_is_moved(
1086                     context,
1087                     InitializationRequiringAction::Update,
1088                     place_span,
1089                     flow_state,
1090                 );
1091             }
1092             MutateMode::JustWrite => {
1093                 self.check_if_assigned_path_is_moved(context, place_span, flow_state);
1094             }
1095         }
1096
1097         let errors_reported = self.access_place(
1098             context,
1099             place_span,
1100             (kind, Write(WriteKind::Mutate)),
1101             // We want immutable upvars to cause an "assignment to immutable var"
1102             // error, not an "reassignment of immutable var" error, because the
1103             // latter can't find a good previous assignment span.
1104             //
1105             // There's probably a better way to do this.
1106             LocalMutationIsAllowed::ExceptUpvars,
1107             flow_state,
1108         );
1109
1110         if !errors_reported.mutability_error {
1111             // check for reassignments to immutable local variables
1112             self.check_if_reassignment_to_immutable_state(context, place_span, flow_state);
1113         }
1114     }
1115
1116     fn consume_rvalue(
1117         &mut self,
1118         context: Context,
1119         (rvalue, span): (&Rvalue<'tcx>, Span),
1120         _location: Location,
1121         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1122     ) {
1123         match *rvalue {
1124             Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
1125                 let access_kind = match bk {
1126                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
1127                     BorrowKind::Unique | BorrowKind::Mut { .. } => {
1128                         let wk = WriteKind::MutableBorrow(bk);
1129                         if allow_two_phase_borrow(&self.tcx, bk) {
1130                             (Deep, Reservation(wk))
1131                         } else {
1132                             (Deep, Write(wk))
1133                         }
1134                     }
1135                 };
1136
1137                 self.access_place(
1138                     context,
1139                     (place, span),
1140                     access_kind,
1141                     LocalMutationIsAllowed::No,
1142                     flow_state,
1143                 );
1144
1145                 self.check_if_path_or_subpath_is_moved(
1146                     context,
1147                     InitializationRequiringAction::Borrow,
1148                     (place, span),
1149                     flow_state,
1150                 );
1151             }
1152
1153             Rvalue::Use(ref operand)
1154             | Rvalue::Repeat(ref operand, _)
1155             | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
1156             | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
1157                 self.consume_operand(context, (operand, span), flow_state)
1158             }
1159
1160             Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
1161                 let af = match *rvalue {
1162                     Rvalue::Len(..) => ArtificialField::ArrayLength,
1163                     Rvalue::Discriminant(..) => ArtificialField::Discriminant,
1164                     _ => unreachable!(),
1165                 };
1166                 self.access_place(
1167                     context,
1168                     (place, span),
1169                     (Shallow(Some(af)), Read(ReadKind::Copy)),
1170                     LocalMutationIsAllowed::No,
1171                     flow_state,
1172                 );
1173                 self.check_if_path_or_subpath_is_moved(
1174                     context,
1175                     InitializationRequiringAction::Use,
1176                     (place, span),
1177                     flow_state,
1178                 );
1179             }
1180
1181             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
1182             | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
1183                 self.consume_operand(context, (operand1, span), flow_state);
1184                 self.consume_operand(context, (operand2, span), flow_state);
1185             }
1186
1187             Rvalue::NullaryOp(_op, _ty) => {
1188                 // nullary ops take no dynamic input; no borrowck effect.
1189                 //
1190                 // FIXME: is above actually true? Do we want to track
1191                 // the fact that uninitialized data can be created via
1192                 // `NullOp::Box`?
1193             }
1194
1195             Rvalue::Aggregate(ref aggregate_kind, ref operands) => {
1196                 // We need to report back the list of mutable upvars that were
1197                 // moved into the closure and subsequently used by the closure,
1198                 // in order to populate our used_mut set.
1199                 match **aggregate_kind {
1200                     AggregateKind::Closure(def_id, _)
1201                     | AggregateKind::Generator(def_id, _, _) => {
1202                         let BorrowCheckResult {
1203                             used_mut_upvars, ..
1204                         } = self.tcx.mir_borrowck(def_id);
1205                         debug!("{:?} used_mut_upvars={:?}", def_id, used_mut_upvars);
1206                         for field in used_mut_upvars {
1207                             // This relies on the current way that by-value
1208                             // captures of a closure are copied/moved directly
1209                             // when generating MIR.
1210                             match operands[field.index()] {
1211                                 Operand::Move(Place::Local(local))
1212                                 | Operand::Copy(Place::Local(local)) => {
1213                                     self.used_mut.insert(local);
1214                                 }
1215                                 Operand::Move(ref place @ Place::Projection(_))
1216                                 | Operand::Copy(ref place @ Place::Projection(_)) => {
1217                                     if let Some(field) = self.is_upvar_field_projection(place) {
1218                                         self.used_mut_upvars.push(field);
1219                                     }
1220                                 }
1221                                 Operand::Move(Place::Static(..))
1222                                 | Operand::Copy(Place::Static(..))
1223                                 | Operand::Constant(..) => {}
1224                             }
1225                         }
1226                     }
1227                     AggregateKind::Adt(..)
1228                     | AggregateKind::Array(..)
1229                     | AggregateKind::Tuple { .. } => (),
1230                 }
1231
1232                 for operand in operands {
1233                     self.consume_operand(context, (operand, span), flow_state);
1234                 }
1235             }
1236         }
1237     }
1238
1239     fn consume_operand(
1240         &mut self,
1241         context: Context,
1242         (operand, span): (&Operand<'tcx>, Span),
1243         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1244     ) {
1245         match *operand {
1246             Operand::Copy(ref place) => {
1247                 // copy of place: check if this is "copy of frozen path"
1248                 // (FIXME: see check_loans.rs)
1249                 self.access_place(
1250                     context,
1251                     (place, span),
1252                     (Deep, Read(ReadKind::Copy)),
1253                     LocalMutationIsAllowed::No,
1254                     flow_state,
1255                 );
1256
1257                 // Finally, check if path was already moved.
1258                 self.check_if_path_or_subpath_is_moved(
1259                     context,
1260                     InitializationRequiringAction::Use,
1261                     (place, span),
1262                     flow_state,
1263                 );
1264             }
1265             Operand::Move(ref place) => {
1266                 // move of place: check if this is move of already borrowed path
1267                 self.access_place(
1268                     context,
1269                     (place, span),
1270                     (Deep, Write(WriteKind::Move)),
1271                     LocalMutationIsAllowed::Yes,
1272                     flow_state,
1273                 );
1274
1275                 // Finally, check if path was already moved.
1276                 self.check_if_path_or_subpath_is_moved(
1277                     context,
1278                     InitializationRequiringAction::Use,
1279                     (place, span),
1280                     flow_state,
1281                 );
1282             }
1283             Operand::Constant(_) => {}
1284         }
1285     }
1286
1287     /// Returns whether a borrow of this place is invalidated when the function
1288     /// exits
1289     fn check_for_invalidation_at_exit(
1290         &mut self,
1291         context: Context,
1292         borrow: &BorrowData<'tcx>,
1293         span: Span,
1294     ) {
1295         debug!("check_for_invalidation_at_exit({:?})", borrow);
1296         let place = &borrow.borrowed_place;
1297         let root_place = self.prefixes(place, PrefixSet::All).last().unwrap();
1298
1299         // FIXME(nll-rfc#40): do more precise destructor tracking here. For now
1300         // we just know that all locals are dropped at function exit (otherwise
1301         // we'll have a memory leak) and assume that all statics have a destructor.
1302         //
1303         // FIXME: allow thread-locals to borrow other thread locals?
1304         let (might_be_alive, will_be_dropped) = match root_place {
1305             Place::Static(statik) => {
1306                 // Thread-locals might be dropped after the function exits, but
1307                 // "true" statics will never be.
1308                 let is_thread_local = self
1309                     .tcx
1310                     .get_attrs(statik.def_id)
1311                     .iter()
1312                     .any(|attr| attr.check_name("thread_local"));
1313
1314                 (true, is_thread_local)
1315             }
1316             Place::Local(_) => {
1317                 // Locals are always dropped at function exit, and if they
1318                 // have a destructor it would've been called already.
1319                 (false, self.locals_are_invalidated_at_exit)
1320             }
1321             Place::Projection(..) => {
1322                 bug!("root of {:?} is a projection ({:?})?", place, root_place)
1323             }
1324         };
1325
1326         if !will_be_dropped {
1327             debug!(
1328                 "place_is_invalidated_at_exit({:?}) - won't be dropped",
1329                 place
1330             );
1331             return;
1332         }
1333
1334         // FIXME: replace this with a proper borrow_conflicts_with_place when
1335         // that is merged.
1336         let sd = if might_be_alive { Deep } else { Shallow(None) };
1337
1338         if places_conflict::places_conflict(self.tcx, self.mir, place, root_place, sd) {
1339             debug!("check_for_invalidation_at_exit({:?}): INVALID", place);
1340             // FIXME: should be talking about the region lifetime instead
1341             // of just a span here.
1342             let span = self.tcx.sess.codemap().end_point(span);
1343             self.report_borrowed_value_does_not_live_long_enough(
1344                 context,
1345                 borrow,
1346                 (place, span),
1347                 None,
1348             )
1349         }
1350     }
1351
1352     /// Reports an error if this is a borrow of local data.
1353     /// This is called for all Yield statements on movable generators
1354     fn check_for_local_borrow(&mut self, borrow: &BorrowData<'tcx>, yield_span: Span) {
1355         debug!("check_for_local_borrow({:?})", borrow);
1356
1357         if borrow_of_local_data(&borrow.borrowed_place) {
1358             self.tcx
1359                 .cannot_borrow_across_generator_yield(
1360                     self.retrieve_borrow_span(borrow),
1361                     yield_span,
1362                     Origin::Mir,
1363                 )
1364                 .emit();
1365         }
1366     }
1367
1368     fn check_activations(
1369         &mut self,
1370         location: Location,
1371         span: Span,
1372         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1373     ) {
1374         if !self.tcx.two_phase_borrows() {
1375             return;
1376         }
1377
1378         // Two-phase borrow support: For each activation that is newly
1379         // generated at this statement, check if it interferes with
1380         // another borrow.
1381         let borrow_set = self.borrow_set.clone();
1382         for &borrow_index in borrow_set.activations_at_location(location) {
1383             let borrow = &borrow_set[borrow_index];
1384
1385             // only mutable borrows should be 2-phase
1386             assert!(match borrow.kind {
1387                 BorrowKind::Shared => false,
1388                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
1389             });
1390
1391             self.access_place(
1392                 ContextKind::Activation.new(location),
1393                 (&borrow.borrowed_place, span),
1394                 (
1395                     Deep,
1396                     Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
1397                 ),
1398                 LocalMutationIsAllowed::No,
1399                 flow_state,
1400             );
1401             // We do not need to call `check_if_path_or_subpath_is_moved`
1402             // again, as we already called it when we made the
1403             // initial reservation.
1404         }
1405     }
1406 }
1407
1408 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
1409     fn check_if_reassignment_to_immutable_state(
1410         &mut self,
1411         context: Context,
1412         (place, span): (&Place<'tcx>, Span),
1413         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1414     ) {
1415         debug!("check_if_reassignment_to_immutable_state({:?})", place);
1416         // determine if this path has a non-mut owner (and thus needs checking).
1417         let err_place = match self.is_mutable(place, LocalMutationIsAllowed::No) {
1418             Ok(..) => return,
1419             Err(place) => place,
1420         };
1421         debug!(
1422             "check_if_reassignment_to_immutable_state({:?}) - is an imm local",
1423             place
1424         );
1425
1426         for i in flow_state.ever_inits.iter_incoming() {
1427             let init = self.move_data.inits[i];
1428             let init_place = &self.move_data.move_paths[init.path].place;
1429             if places_conflict::places_conflict(self.tcx, self.mir, &init_place, place, Deep) {
1430                 self.report_illegal_reassignment(context, (place, span), init.span, err_place);
1431                 break;
1432             }
1433         }
1434     }
1435
1436     fn check_if_full_path_is_moved(
1437         &mut self,
1438         context: Context,
1439         desired_action: InitializationRequiringAction,
1440         place_span: (&Place<'tcx>, Span),
1441         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1442     ) {
1443         // FIXME: analogous code in check_loans first maps `place` to
1444         // its base_path ... but is that what we want here?
1445         let place = self.base_path(place_span.0);
1446
1447         let maybe_uninits = &flow_state.uninits;
1448         let curr_move_outs = &flow_state.move_outs;
1449
1450         // Bad scenarios:
1451         //
1452         // 1. Move of `a.b.c`, use of `a.b.c`
1453         // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
1454         // 3. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
1455         //    partial initialization support, one might have `a.x`
1456         //    initialized but not `a.b`.
1457         //
1458         // OK scenarios:
1459         //
1460         // 4. Move of `a.b.c`, use of `a.b.d`
1461         // 5. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1462         // 6. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1463         //    must have been initialized for the use to be sound.
1464         // 7. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1465
1466         // The dataflow tracks shallow prefixes distinctly (that is,
1467         // field-accesses on P distinctly from P itself), in order to
1468         // track substructure initialization separately from the whole
1469         // structure.
1470         //
1471         // E.g., when looking at (*a.b.c).d, if the closest prefix for
1472         // which we have a MovePath is `a.b`, then that means that the
1473         // initialization state of `a.b` is all we need to inspect to
1474         // know if `a.b.c` is valid (and from that we infer that the
1475         // dereference and `.d` access is also valid, since we assume
1476         // `a.b.c` is assigned a reference to a initialized and
1477         // well-formed record structure.)
1478
1479         // Therefore, if we seek out the *closest* prefix for which we
1480         // have a MovePath, that should capture the initialization
1481         // state for the place scenario.
1482         //
1483         // This code covers scenarios 1, 2, and 3.
1484
1485         debug!("check_if_full_path_is_moved place: {:?}", place);
1486         match self.move_path_closest_to(place) {
1487             Ok(mpi) => {
1488                 if maybe_uninits.contains(&mpi) {
1489                     self.report_use_of_moved_or_uninitialized(
1490                         context,
1491                         desired_action,
1492                         place_span,
1493                         mpi,
1494                         curr_move_outs,
1495                     );
1496                     return; // don't bother finding other problems.
1497                 }
1498             }
1499             Err(NoMovePathFound::ReachedStatic) => {
1500                 // Okay: we do not build MoveData for static variables
1501             } // Only query longest prefix with a MovePath, not further
1502               // ancestors; dataflow recurs on children when parents
1503               // move (to support partial (re)inits).
1504               //
1505               // (I.e. querying parents breaks scenario 7; but may want
1506               // to do such a query based on partial-init feature-gate.)
1507         }
1508     }
1509
1510     fn check_if_path_or_subpath_is_moved(
1511         &mut self,
1512         context: Context,
1513         desired_action: InitializationRequiringAction,
1514         place_span: (&Place<'tcx>, Span),
1515         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1516     ) {
1517         // FIXME: analogous code in check_loans first maps `place` to
1518         // its base_path ... but is that what we want here?
1519         let place = self.base_path(place_span.0);
1520
1521         let maybe_uninits = &flow_state.uninits;
1522         let curr_move_outs = &flow_state.move_outs;
1523
1524         // Bad scenarios:
1525         //
1526         // 1. Move of `a.b.c`, use of `a` or `a.b`
1527         //    partial initialization support, one might have `a.x`
1528         //    initialized but not `a.b`.
1529         // 2. All bad scenarios from `check_if_full_path_is_moved`
1530         //
1531         // OK scenarios:
1532         //
1533         // 3. Move of `a.b.c`, use of `a.b.d`
1534         // 4. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1535         // 5. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1536         //    must have been initialized for the use to be sound.
1537         // 6. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1538
1539         self.check_if_full_path_is_moved(context, desired_action, place_span, flow_state);
1540
1541         // A move of any shallow suffix of `place` also interferes
1542         // with an attempt to use `place`. This is scenario 3 above.
1543         //
1544         // (Distinct from handling of scenarios 1+2+4 above because
1545         // `place` does not interfere with suffixes of its prefixes,
1546         // e.g. `a.b.c` does not interfere with `a.b.d`)
1547         //
1548         // This code covers scenario 1.
1549
1550         debug!("check_if_path_or_subpath_is_moved place: {:?}", place);
1551         if let Some(mpi) = self.move_path_for_place(place) {
1552             if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) {
1553                 self.report_use_of_moved_or_uninitialized(
1554                     context,
1555                     desired_action,
1556                     place_span,
1557                     child_mpi,
1558                     curr_move_outs,
1559                 );
1560                 return; // don't bother finding other problems.
1561             }
1562         }
1563     }
1564
1565     /// Currently MoveData does not store entries for all places in
1566     /// the input MIR. For example it will currently filter out
1567     /// places that are Copy; thus we do not track places of shared
1568     /// reference type. This routine will walk up a place along its
1569     /// prefixes, searching for a foundational place that *is*
1570     /// tracked in the MoveData.
1571     ///
1572     /// An Err result includes a tag indicated why the search failed.
1573     /// Currently this can only occur if the place is built off of a
1574     /// static variable, as we do not track those in the MoveData.
1575     fn move_path_closest_to(
1576         &mut self,
1577         place: &Place<'tcx>,
1578     ) -> Result<MovePathIndex, NoMovePathFound> {
1579         let mut last_prefix = place;
1580         for prefix in self.prefixes(place, PrefixSet::All) {
1581             if let Some(mpi) = self.move_path_for_place(prefix) {
1582                 return Ok(mpi);
1583             }
1584             last_prefix = prefix;
1585         }
1586         match *last_prefix {
1587             Place::Local(_) => panic!("should have move path for every Local"),
1588             Place::Projection(_) => panic!("PrefixSet::All meant don't stop for Projection"),
1589             Place::Static(_) => return Err(NoMovePathFound::ReachedStatic),
1590         }
1591     }
1592
1593     fn move_path_for_place(&mut self, place: &Place<'tcx>) -> Option<MovePathIndex> {
1594         // If returns None, then there is no move path corresponding
1595         // to a direct owner of `place` (which means there is nothing
1596         // that borrowck tracks for its analysis).
1597
1598         match self.move_data.rev_lookup.find(place) {
1599             LookupResult::Parent(_) => None,
1600             LookupResult::Exact(mpi) => Some(mpi),
1601         }
1602     }
1603
1604     fn check_if_assigned_path_is_moved(
1605         &mut self,
1606         context: Context,
1607         (place, span): (&Place<'tcx>, Span),
1608         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1609     ) {
1610         debug!("check_if_assigned_path_is_moved place: {:?}", place);
1611         // recur down place; dispatch to external checks when necessary
1612         let mut place = place;
1613         loop {
1614             match *place {
1615                 Place::Local(_) | Place::Static(_) => {
1616                     // assigning to `x` does not require `x` be initialized.
1617                     break;
1618                 }
1619                 Place::Projection(ref proj) => {
1620                     let Projection { ref base, ref elem } = **proj;
1621                     match *elem {
1622                         ProjectionElem::Index(_/*operand*/) |
1623                         ProjectionElem::ConstantIndex { .. } |
1624                         // assigning to P[i] requires P to be valid.
1625                         ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
1626                         // assigning to (P->variant) is okay if assigning to `P` is okay
1627                         //
1628                         // FIXME: is this true even if P is a adt with a dtor?
1629                         { }
1630
1631                         // assigning to (*P) requires P to be initialized
1632                         ProjectionElem::Deref => {
1633                             self.check_if_full_path_is_moved(
1634                                 context, InitializationRequiringAction::Use,
1635                                 (base, span), flow_state);
1636                             // (base initialized; no need to
1637                             // recur further)
1638                             break;
1639                         }
1640
1641                         ProjectionElem::Subslice { .. } => {
1642                             panic!("we don't allow assignments to subslices, context: {:?}",
1643                                    context);
1644                         }
1645
1646                         ProjectionElem::Field(..) => {
1647                             // if type of `P` has a dtor, then
1648                             // assigning to `P.f` requires `P` itself
1649                             // be already initialized
1650                             let tcx = self.tcx;
1651                             match base.ty(self.mir, tcx).to_ty(tcx).sty {
1652                                 ty::TyAdt(def, _) if def.has_dtor(tcx) => {
1653
1654                                     // FIXME: analogous code in
1655                                     // check_loans.rs first maps
1656                                     // `base` to its base_path.
1657
1658                                     self.check_if_path_or_subpath_is_moved(
1659                                         context, InitializationRequiringAction::Assignment,
1660                                         (base, span), flow_state);
1661
1662                                     // (base initialized; no need to
1663                                     // recur further)
1664                                     break;
1665                                 }
1666                                 _ => {}
1667                             }
1668                         }
1669                     }
1670
1671                     place = base;
1672                     continue;
1673                 }
1674             }
1675         }
1676     }
1677
1678
1679     /// Check the permissions for the given place and read or write kind
1680     ///
1681     /// Returns true if an error is reported, false otherwise.
1682     fn check_access_permissions(
1683         &mut self,
1684         (place, span): (&Place<'tcx>, Span),
1685         kind: ReadOrWrite,
1686         is_local_mutation_allowed: LocalMutationIsAllowed,
1687         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1688         location: Location,
1689     ) -> bool {
1690         debug!(
1691             "check_access_permissions({:?}, {:?}, {:?})",
1692             place, kind, is_local_mutation_allowed
1693         );
1694
1695         let error_access;
1696         let the_place_err;
1697
1698         match kind {
1699             Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1700             | Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. }))
1701             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1702             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. })) => {
1703                 let is_local_mutation_allowed = match borrow_kind {
1704                     BorrowKind::Unique => LocalMutationIsAllowed::Yes,
1705                     BorrowKind::Mut { .. } => is_local_mutation_allowed,
1706                     BorrowKind::Shared => unreachable!(),
1707                 };
1708                 match self.is_mutable(place, is_local_mutation_allowed) {
1709                     Ok(root_place) => {
1710                         self.add_used_mut(root_place, flow_state);
1711                         return false;
1712                     }
1713                     Err(place_err) => {
1714                         error_access = AccessKind::MutableBorrow;
1715                         the_place_err = place_err;
1716                     }
1717                 }
1718             }
1719             Reservation(WriteKind::Mutate) | Write(WriteKind::Mutate) => {
1720                 match self.is_mutable(place, is_local_mutation_allowed) {
1721                     Ok(root_place) => {
1722                         self.add_used_mut(root_place, flow_state);
1723                         return false;
1724                     }
1725                     Err(place_err) => {
1726                         error_access = AccessKind::Mutate;
1727                         the_place_err = place_err;
1728                     }
1729                 }
1730             }
1731
1732             Reservation(WriteKind::Move)
1733             | Write(WriteKind::Move)
1734             | Reservation(WriteKind::StorageDeadOrDrop)
1735             | Reservation(WriteKind::MutableBorrow(BorrowKind::Shared))
1736             | Write(WriteKind::StorageDeadOrDrop)
1737             | Write(WriteKind::MutableBorrow(BorrowKind::Shared)) => {
1738                 if let Err(_place_err) = self.is_mutable(place, is_local_mutation_allowed) {
1739                     self.tcx.sess.delay_span_bug(
1740                         span,
1741                         &format!(
1742                             "Accessing `{:?}` with the kind `{:?}` shouldn't be possible",
1743                             place, kind
1744                         ),
1745                     );
1746                 }
1747                 return false;
1748             }
1749             Activation(..) => {
1750                 // permission checks are done at Reservation point.
1751                 return false;
1752             }
1753             Read(ReadKind::Borrow(BorrowKind::Unique))
1754             | Read(ReadKind::Borrow(BorrowKind::Mut { .. }))
1755             | Read(ReadKind::Borrow(BorrowKind::Shared))
1756             | Read(ReadKind::Copy) => {
1757                 // Access authorized
1758                 return false;
1759             }
1760         }
1761
1762         // at this point, we have set up the error reporting state.
1763         self.report_mutability_error(
1764             place,
1765             span,
1766             the_place_err,
1767             error_access,
1768             location,
1769         );
1770         return true;
1771     }
1772
1773     /// Adds the place into the used mutable variables set
1774     fn add_used_mut<'d>(
1775         &mut self,
1776         root_place: RootPlace<'d, 'tcx>,
1777         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1778     ) {
1779         match root_place {
1780             RootPlace {
1781                 place: Place::Local(local),
1782                 is_local_mutation_allowed,
1783             } => {
1784                 if is_local_mutation_allowed != LocalMutationIsAllowed::Yes {
1785                     // If the local may be initialized, and it is now currently being
1786                     // mutated, then it is justified to be annotated with the `mut`
1787                     // keyword, since the mutation may be a possible reassignment.
1788                     let mpi = self.move_data.rev_lookup.find_local(*local);
1789                     let ii = &self.move_data.init_path_map[mpi];
1790                     for index in ii {
1791                         if flow_state.ever_inits.contains(index) {
1792                             self.used_mut.insert(*local);
1793                             break;
1794                         }
1795                     }
1796                 }
1797             }
1798             RootPlace {
1799                 place: _,
1800                 is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1801             } => {}
1802             RootPlace {
1803                 place: place @ Place::Projection(_),
1804                 is_local_mutation_allowed: _,
1805             } => {
1806                 if let Some(field) = self.is_upvar_field_projection(&place) {
1807                     self.used_mut_upvars.push(field);
1808                 }
1809             }
1810             RootPlace {
1811                 place: Place::Static(..),
1812                 is_local_mutation_allowed: _,
1813             } => {}
1814         }
1815     }
1816
1817     /// Whether this value be written or borrowed mutably.
1818     /// Returns the root place if the place passed in is a projection.
1819     fn is_mutable<'d>(
1820         &self,
1821         place: &'d Place<'tcx>,
1822         is_local_mutation_allowed: LocalMutationIsAllowed,
1823     ) -> Result<RootPlace<'d, 'tcx>, &'d Place<'tcx>> {
1824         match *place {
1825             Place::Local(local) => {
1826                 let local = &self.mir.local_decls[local];
1827                 match local.mutability {
1828                     Mutability::Not => match is_local_mutation_allowed {
1829                         LocalMutationIsAllowed::Yes => Ok(RootPlace {
1830                             place,
1831                             is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1832                         }),
1833                         LocalMutationIsAllowed::ExceptUpvars => Ok(RootPlace {
1834                             place,
1835                             is_local_mutation_allowed: LocalMutationIsAllowed::ExceptUpvars,
1836                         }),
1837                         LocalMutationIsAllowed::No => Err(place),
1838                     },
1839                     Mutability::Mut => Ok(RootPlace {
1840                         place,
1841                         is_local_mutation_allowed,
1842                     }),
1843                 }
1844             }
1845             Place::Static(ref static_) => {
1846                 if self.tcx.is_static(static_.def_id) != Some(hir::Mutability::MutMutable) {
1847                     Err(place)
1848                 } else {
1849                     Ok(RootPlace {
1850                         place,
1851                         is_local_mutation_allowed,
1852                     })
1853                 }
1854             }
1855             Place::Projection(ref proj) => {
1856                 match proj.elem {
1857                     ProjectionElem::Deref => {
1858                         let base_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
1859
1860                         // Check the kind of deref to decide
1861                         match base_ty.sty {
1862                             ty::TyRef(_, _, mutbl) => {
1863                                 match mutbl {
1864                                     // Shared borrowed data is never mutable
1865                                     hir::MutImmutable => Err(place),
1866                                     // Mutably borrowed data is mutable, but only if we have a
1867                                     // unique path to the `&mut`
1868                                     hir::MutMutable => {
1869                                         let mode = match self.is_upvar_field_projection(&proj.base)
1870                                         {
1871                                             Some(field)
1872                                                 if {
1873                                                     self.mir.upvar_decls[field.index()].by_ref
1874                                                 } =>
1875                                             {
1876                                                 is_local_mutation_allowed
1877                                             }
1878                                             _ => LocalMutationIsAllowed::Yes,
1879                                         };
1880
1881                                         self.is_mutable(&proj.base, mode)
1882                                     }
1883                                 }
1884                             }
1885                             ty::TyRawPtr(tnm) => {
1886                                 match tnm.mutbl {
1887                                     // `*const` raw pointers are not mutable
1888                                     hir::MutImmutable => return Err(place),
1889                                     // `*mut` raw pointers are always mutable, regardless of
1890                                     // context. The users have to check by themselves.
1891                                     hir::MutMutable => {
1892                                         return Ok(RootPlace {
1893                                             place,
1894                                             is_local_mutation_allowed,
1895                                         });
1896                                     }
1897                                 }
1898                             }
1899                             // `Box<T>` owns its content, so mutable if its location is mutable
1900                             _ if base_ty.is_box() => {
1901                                 self.is_mutable(&proj.base, is_local_mutation_allowed)
1902                             }
1903                             // Deref should only be for reference, pointers or boxes
1904                             _ => bug!("Deref of unexpected type: {:?}", base_ty),
1905                         }
1906                     }
1907                     // All other projections are owned by their base path, so mutable if
1908                     // base path is mutable
1909                     ProjectionElem::Field(..)
1910                     | ProjectionElem::Index(..)
1911                     | ProjectionElem::ConstantIndex { .. }
1912                     | ProjectionElem::Subslice { .. }
1913                     | ProjectionElem::Downcast(..) => {
1914                         if let Some(field) = self.is_upvar_field_projection(place) {
1915                             let decl = &self.mir.upvar_decls[field.index()];
1916                             debug!(
1917                                 "decl.mutability={:?} local_mutation_is_allowed={:?} place={:?}",
1918                                 decl, is_local_mutation_allowed, place
1919                             );
1920                             match (decl.mutability, is_local_mutation_allowed) {
1921                                 (Mutability::Not, LocalMutationIsAllowed::No)
1922                                 | (Mutability::Not, LocalMutationIsAllowed::ExceptUpvars) => {
1923                                     Err(place)
1924                                 }
1925                                 (Mutability::Not, LocalMutationIsAllowed::Yes)
1926                                 | (Mutability::Mut, _) => {
1927                                     // Subtle: this is an upvar
1928                                     // reference, so it looks like
1929                                     // `self.foo` -- we want to double
1930                                     // check that the context `*self`
1931                                     // is mutable (i.e., this is not a
1932                                     // `Fn` closure).  But if that
1933                                     // check succeeds, we want to
1934                                     // *blame* the mutability on
1935                                     // `place` (that is,
1936                                     // `self.foo`). This is used to
1937                                     // propagate the info about
1938                                     // whether mutability declarations
1939                                     // are used outwards, so that we register
1940                                     // the outer variable as mutable. Otherwise a
1941                                     // test like this fails to record the `mut`
1942                                     // as needed:
1943                                     //
1944                                     // ```
1945                                     // fn foo<F: FnOnce()>(_f: F) { }
1946                                     // fn main() {
1947                                     //     let var = Vec::new();
1948                                     //     foo(move || {
1949                                     //         var.push(1);
1950                                     //     });
1951                                     // }
1952                                     // ```
1953                                     let _ = self.is_mutable(&proj.base, is_local_mutation_allowed)?;
1954                                     Ok(RootPlace {
1955                                         place,
1956                                         is_local_mutation_allowed,
1957                                     })
1958                                 }
1959                             }
1960                         } else {
1961                             self.is_mutable(&proj.base, is_local_mutation_allowed)
1962                         }
1963                     }
1964                 }
1965             }
1966         }
1967     }
1968
1969     /// If this is a field projection, and the field is being projected from a closure type,
1970     /// then returns the index of the field being projected. Note that this closure will always
1971     /// be `self` in the current MIR, because that is the only time we directly access the fields
1972     /// of a closure type.
1973     fn is_upvar_field_projection(&self, place: &Place<'tcx>) -> Option<Field> {
1974         match *place {
1975             Place::Projection(ref proj) => match proj.elem {
1976                 ProjectionElem::Field(field, _ty) => {
1977                     let base_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
1978
1979                     if base_ty.is_closure() || base_ty.is_generator() {
1980                         Some(field)
1981                     } else {
1982                         None
1983                     }
1984                 }
1985                 _ => None,
1986             },
1987             _ => None,
1988         }
1989     }
1990 }
1991
1992 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
1993 enum NoMovePathFound {
1994     ReachedStatic,
1995 }
1996
1997 /// The degree of overlap between 2 places for borrow-checking.
1998 enum Overlap {
1999     /// The places might partially overlap - in this case, we give
2000     /// up and say that they might conflict. This occurs when
2001     /// different fields of a union are borrowed. For example,
2002     /// if `u` is a union, we have no way of telling how disjoint
2003     /// `u.a.x` and `a.b.y` are.
2004     Arbitrary,
2005     /// The places have the same type, and are either completely disjoint
2006     /// or equal - i.e. they can't "partially" overlap as can occur with
2007     /// unions. This is the "base case" on which we recur for extensions
2008     /// of the place.
2009     EqualOrDisjoint,
2010     /// The places are disjoint, so we know all extensions of them
2011     /// will also be disjoint.
2012     Disjoint,
2013 }
2014
2015 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
2016     // FIXME (#16118): function intended to allow the borrow checker
2017     // to be less precise in its handling of Box while still allowing
2018     // moves out of a Box. They should be removed when/if we stop
2019     // treating Box specially (e.g. when/if DerefMove is added...)
2020
2021     fn base_path<'d>(&self, place: &'d Place<'tcx>) -> &'d Place<'tcx> {
2022         //! Returns the base of the leftmost (deepest) dereference of an
2023         //! Box in `place`. If there is no dereference of an Box
2024         //! in `place`, then it just returns `place` itself.
2025
2026         let mut cursor = place;
2027         let mut deepest = place;
2028         loop {
2029             let proj = match *cursor {
2030                 Place::Local(..) | Place::Static(..) => return deepest,
2031                 Place::Projection(ref proj) => proj,
2032             };
2033             if proj.elem == ProjectionElem::Deref
2034                 && place.ty(self.mir, self.tcx).to_ty(self.tcx).is_box()
2035             {
2036                 deepest = &proj.base;
2037             }
2038             cursor = &proj.base;
2039         }
2040     }
2041 }
2042
2043 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2044 struct Context {
2045     kind: ContextKind,
2046     loc: Location,
2047 }
2048
2049 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2050 enum ContextKind {
2051     Activation,
2052     AssignLhs,
2053     AssignRhs,
2054     SetDiscrim,
2055     InlineAsm,
2056     SwitchInt,
2057     Drop,
2058     DropAndReplace,
2059     CallOperator,
2060     CallOperand,
2061     CallDest,
2062     Assert,
2063     Yield,
2064     ReadForMatch,
2065     StorageDead,
2066 }
2067
2068 impl ContextKind {
2069     fn new(self, loc: Location) -> Context {
2070         Context {
2071             kind: self,
2072             loc: loc,
2073         }
2074     }
2075 }