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