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