src/librustc_mir/borrow_check/mod.rs

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