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