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};
  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                 self.visit_terminator_drop(loc, term, flow_state, drop_place, drop_place_ty, span);
 602             }
 603             TerminatorKind::DropAndReplace {
 604                 location: ref drop_place,
 605                 value: ref new_value,
 606                 target: _,
 607                 unwind: _,
 608             } => {
 609                 self.mutate_place(
 610                     ContextKind::DropAndReplace.new(loc),
 611                     (drop_place, span),
 612                     Deep,
 613                     JustWrite,
 614                     flow_state,
 615                 );
 616                 self.consume_operand(
 617                     ContextKind::DropAndReplace.new(loc),
 618                     (new_value, span),
 619                     flow_state,
 620                 );
 621             }
 622             TerminatorKind::Call {
 623                 ref func,
 624                 ref args,
 625                 ref destination,
 626                 cleanup: _,
 627             } => {
 628                 self.consume_operand(ContextKind::CallOperator.new(loc), (func, span), flow_state);
 629                 for arg in args {
 630                     self.consume_operand(
 631                         ContextKind::CallOperand.new(loc),
 632                         (arg, span),
 633                         flow_state,
 634                     );
 635                 }
 636                 if let Some((ref dest, _ /*bb*/)) = *destination {
 637                     self.mutate_place(
 638                         ContextKind::CallDest.new(loc),
 639                         (dest, span),
 640                         Deep,
 641                         JustWrite,
 642                         flow_state,
 643                     );
 644                 }
 645             }
 646             TerminatorKind::Assert {
 647                 ref cond,
 648                 expected: _,
 649                 ref msg,
 650                 target: _,
 651                 cleanup: _,
 652             } => {
 653                 self.consume_operand(ContextKind::Assert.new(loc), (cond, span), flow_state);
 654                 use rustc::mir::interpret::EvalErrorKind::BoundsCheck;
 655                 if let BoundsCheck { ref len, ref index } = *msg {
 656                     self.consume_operand(ContextKind::Assert.new(loc), (len, span), flow_state);
 657                     self.consume_operand(ContextKind::Assert.new(loc), (index, span), flow_state);
 658                 }
 659             }
 660
 661             TerminatorKind::Yield {
 662                 ref value,
 663                 resume: _,
 664                 drop: _,
 665             } => {
 666                 self.consume_operand(ContextKind::Yield.new(loc), (value, span), flow_state);
 667
 668                 if self.movable_generator {
 669                     // Look for any active borrows to locals
 670                     let borrow_set = self.borrow_set.clone();
 671                     flow_state.with_outgoing_borrows(|borrows| {
 672                         for i in borrows {
 673                             let borrow = &borrow_set[i];
 674                             self.check_for_local_borrow(borrow, span);
 675                         }
 676                     });
 677                 }
 678             }
 679
 680             TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
 681                 // Returning from the function implicitly kills storage for all locals and statics.
 682                 // Often, the storage will already have been killed by an explicit
 683                 // StorageDead, but we don't always emit those (notably on unwind paths),
 684                 // so this "extra check" serves as a kind of backup.
 685                 let borrow_set = self.borrow_set.clone();
 686                 flow_state.with_outgoing_borrows(|borrows| {
 687                     for i in borrows {
 688                         let borrow = &borrow_set[i];
 689                         let context = ContextKind::StorageDead.new(loc);
 690                         self.check_for_invalidation_at_exit(context, borrow, span);
 691                     }
 692                 });
 693             }
 694             TerminatorKind::Goto { target: _ }
 695             | TerminatorKind::Abort
 696             | TerminatorKind::Unreachable
 697             | TerminatorKind::FalseEdges {
 698                 real_target: _,
 699                 imaginary_targets: _,
 700             }
 701             | TerminatorKind::FalseUnwind {
 702                 real_target: _,
 703                 unwind: _,
 704             } => {
 705                 // no data used, thus irrelevant to borrowck
 706             }
 707         }
 708     }
 709 }
 710
 711 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 712 enum MutateMode {
 713     JustWrite,
 714     WriteAndRead,
 715 }
 716
 717 use self::ReadOrWrite::{Activation, Read, Reservation, Write};
 718 use self::ShallowOrDeep::{Deep, Shallow};
 719
 720 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 721 enum ArtificialField {
 722     Discriminant,
 723     ArrayLength,
 724 }
 725
 726 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 727 enum ShallowOrDeep {
 728     /// From the RFC: "A *shallow* access means that the immediate
 729     /// fields reached at P are accessed, but references or pointers
 730     /// found within are not dereferenced. Right now, the only access
 731     /// that is shallow is an assignment like `x = ...;`, which would
 732     /// be a *shallow write* of `x`."
 733     Shallow(Option<ArtificialField>),
 734
 735     /// From the RFC: "A *deep* access means that all data reachable
 736     /// through the given place may be invalidated or accesses by
 737     /// this action."
 738     Deep,
 739 }
 740
 741 /// Kind of access to a value: read or write
 742 /// (For informational purposes only)
 743 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 744 enum ReadOrWrite {
 745     /// From the RFC: "A *read* means that the existing data may be
 746     /// read, but will not be changed."
 747     Read(ReadKind),
 748
 749     /// From the RFC: "A *write* means that the data may be mutated to
 750     /// new values or otherwise invalidated (for example, it could be
 751     /// de-initialized, as in a move operation).
 752     Write(WriteKind),
 753
 754     /// For two-phase borrows, we distinguish a reservation (which is treated
 755     /// like a Read) from an activation (which is treated like a write), and
 756     /// each of those is furthermore distinguished from Reads/Writes above.
 757     Reservation(WriteKind),
 758     Activation(WriteKind, BorrowIndex),
 759 }
 760
 761 /// Kind of read access to a value
 762 /// (For informational purposes only)
 763 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 764 enum ReadKind {
 765     Borrow(BorrowKind),
 766     Copy,
 767 }
 768
 769 /// Kind of write access to a value
 770 /// (For informational purposes only)
 771 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 772 enum WriteKind {
 773     StorageDeadOrDrop,
 774     MutableBorrow(BorrowKind),
 775     Mutate,
 776     Move,
 777 }
 778
 779 /// When checking permissions for a place access, this flag is used to indicate that an immutable
 780 /// local place can be mutated.
 781 ///
 782 /// FIXME: @nikomatsakis suggested that this flag could be removed with the following modifications:
 783 /// - Merge `check_access_permissions()` and `check_if_reassignment_to_immutable_state()`
 784 /// - Split `is_mutable()` into `is_assignable()` (can be directly assigned) and
 785 ///   `is_declared_mutable()`
 786 /// - Take flow state into consideration in `is_assignable()` for local variables
 787 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 788 enum LocalMutationIsAllowed {
 789     Yes,
 790     /// We want use of immutable upvars to cause a "write to immutable upvar"
 791     /// error, not an "reassignment" error.
 792     ExceptUpvars,
 793     No,
 794 }
 795
 796 struct AccessErrorsReported {
 797     mutability_error: bool,
 798     #[allow(dead_code)]
 799     conflict_error: bool,
 800 }
 801
 802 #[derive(Copy, Clone)]
 803 enum InitializationRequiringAction {
 804     Update,
 805     Borrow,
 806     Use,
 807     Assignment,
 808 }
 809
 810 struct RootPlace<'d, 'tcx: 'd> {
 811     place: &'d Place<'tcx>,
 812     is_local_mutation_allowed: LocalMutationIsAllowed,
 813 }
 814
 815 impl InitializationRequiringAction {
 816     fn as_noun(self) -> &'static str {
 817         match self {
 818             InitializationRequiringAction::Update => "update",
 819             InitializationRequiringAction::Borrow => "borrow",
 820             InitializationRequiringAction::Use => "use",
 821             InitializationRequiringAction::Assignment => "assign",
 822         }
 823     }
 824
 825     fn as_verb_in_past_tense(self) -> &'static str {
 826         match self {
 827             InitializationRequiringAction::Update => "updated",
 828             InitializationRequiringAction::Borrow => "borrowed",
 829             InitializationRequiringAction::Use => "used",
 830             InitializationRequiringAction::Assignment => "assigned",
 831         }
 832     }
 833 }
 834
 835 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
 836     /// Invokes `access_place` as appropriate for dropping the value
 837     /// at `drop_place`. Note that the *actual* `Drop` in the MIR is
 838     /// always for a variable (e.g., `Drop(x)`) -- but we recursively
 839     /// break this variable down into subpaths (e.g., `Drop(x.foo)`)
 840     /// to indicate more precisely which fields might actually be
 841     /// accessed by a destructor.
 842     fn visit_terminator_drop(
 843         &mut self,
 844         loc: Location,
 845         term: &Terminator<'tcx>,
 846         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 847         drop_place: &Place<'tcx>,
 848         erased_drop_place_ty: ty::Ty<'gcx>,
 849         span: Span,
 850     ) {
 851         let gcx = self.tcx.global_tcx();
 852         let drop_field = |mir: &mut MirBorrowckCtxt<'cx, 'gcx, 'tcx>,
 853                           (index, field): (usize, ty::Ty<'gcx>)| {
 854             let field_ty = gcx.normalize_erasing_regions(mir.param_env, field);
 855             let place = drop_place.clone().field(Field::new(index), field_ty);
 856
 857             mir.visit_terminator_drop(loc, term, flow_state, &place, field_ty, span);
 858         };
 859
 860         match erased_drop_place_ty.sty {
 861             // When a struct is being dropped, we need to check
 862             // whether it has a destructor, if it does, then we can
 863             // call it, if it does not then we need to check the
 864             // individual fields instead. This way if `foo` has a
 865             // destructor but `bar` does not, we will only check for
 866             // borrows of `x.foo` and not `x.bar`. See #47703.
 867             ty::TyAdt(def, substs) if def.is_struct() && !def.has_dtor(self.tcx) => {
 868                 def.all_fields()
 869                     .map(|field| field.ty(gcx, substs))
 870                     .enumerate()
 871                     .for_each(|field| drop_field(self, field));
 872             }
 873             // Same as above, but for tuples.
 874             ty::TyTuple(tys) => {
 875                 tys.iter()
 876                     .cloned()
 877                     .enumerate()
 878                     .for_each(|field| drop_field(self, field));
 879             }
 880             // Closures also have disjoint fields, but they are only
 881             // directly accessed in the body of the closure.
 882             ty::TyClosure(def, substs)
 883                 if *drop_place == Place::Local(Local::new(1))
 884                     && !self.mir.upvar_decls.is_empty() =>
 885             {
 886                 substs
 887                     .upvar_tys(def, self.tcx)
 888                     .enumerate()
 889                     .for_each(|field| drop_field(self, field));
 890             }
 891             // Generators also have disjoint fields, but they are only
 892             // directly accessed in the body of the generator.
 893             ty::TyGenerator(def, substs, _)
 894                 if *drop_place == Place::Local(Local::new(1))
 895                     && !self.mir.upvar_decls.is_empty() =>
 896             {
 897                 substs
 898                     .upvar_tys(def, self.tcx)
 899                     .enumerate()
 900                     .for_each(|field| drop_field(self, field));
 901             }
 902             _ => {
 903                 // We have now refined the type of the value being
 904                 // dropped (potentially) to just the type of a
 905                 // subfield; so check whether that field's type still
 906                 // "needs drop". If so, we assume that the destructor
 907                 // may access any data it likes (i.e., a Deep Write).
 908                 if erased_drop_place_ty.needs_drop(gcx, self.param_env) {
 909                     self.access_place(
 910                         ContextKind::Drop.new(loc),
 911                         (drop_place, span),
 912                         (Deep, Write(WriteKind::StorageDeadOrDrop)),
 913                         LocalMutationIsAllowed::Yes,
 914                         flow_state,
 915                     );
 916                 }
 917             }
 918         }
 919     }
 920
 921     /// Checks an access to the given place to see if it is allowed. Examines the set of borrows
 922     /// that are in scope, as well as which paths have been initialized, to ensure that (a) the
 923     /// place is initialized and (b) it is not borrowed in some way that would prevent this
 924     /// access.
 925     ///
 926     /// Returns true if an error is reported, false otherwise.
 927     fn access_place(
 928         &mut self,
 929         context: Context,
 930         place_span: (&Place<'tcx>, Span),
 931         kind: (ShallowOrDeep, ReadOrWrite),
 932         is_local_mutation_allowed: LocalMutationIsAllowed,
 933         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 934     ) -> AccessErrorsReported {
 935         let (sd, rw) = kind;
 936
 937         if let Activation(_, borrow_index) = rw {
 938             if self.reservation_error_reported.contains(&place_span.0) {
 939                 debug!(
 940                     "skipping access_place for activation of invalid reservation \
 941                      place: {:?} borrow_index: {:?}",
 942                     place_span.0, borrow_index
 943                 );
 944                 return AccessErrorsReported {
 945                     mutability_error: false,
 946                     conflict_error: true,
 947                 };
 948             }
 949         }
 950
 951         if self
 952             .access_place_error_reported
 953             .contains(&(place_span.0.clone(), place_span.1))
 954         {
 955             debug!(
 956                 "access_place: suppressing error place_span=`{:?}` kind=`{:?}`",
 957                 place_span, kind
 958             );
 959             return AccessErrorsReported {
 960                 mutability_error: false,
 961                 conflict_error: true,
 962             };
 963         }
 964
 965         let mutability_error =
 966             self.check_access_permissions(
 967                 place_span,
 968                 rw,
 969                 is_local_mutation_allowed,
 970                 flow_state,
 971                 context.loc,
 972             );
 973         let conflict_error =
 974             self.check_access_for_conflict(context, place_span, sd, rw, flow_state);
 975
 976         if conflict_error || mutability_error {
 977             debug!(
 978                 "access_place: logging error place_span=`{:?}` kind=`{:?}`",
 979                 place_span, kind
 980             );
 981             self.access_place_error_reported
 982                 .insert((place_span.0.clone(), place_span.1));
 983         }
 984
 985         AccessErrorsReported {
 986             mutability_error,
 987             conflict_error,
 988         }
 989     }
 990
 991     fn check_access_for_conflict(
 992         &mut self,
 993         context: Context,
 994         place_span: (&Place<'tcx>, Span),
 995         sd: ShallowOrDeep,
 996         rw: ReadOrWrite,
 997         flow_state: &Flows<'cx, 'gcx, 'tcx>,
 998     ) -> bool {
 999         debug!(
1000             "check_access_for_conflict(context={:?}, place_span={:?}, sd={:?}, rw={:?})",
1001             context, place_span, sd, rw,
1002         );
1003
1004         let mut error_reported = false;
1005         let tcx = self.tcx;
1006         let mir = self.mir;
1007         let location = self.location_table.start_index(context.loc);
1008         let borrow_set = self.borrow_set.clone();
1009         each_borrow_involving_path(
1010             self,
1011             tcx,
1012             mir,
1013             context,
1014             (sd, place_span.0),
1015             &borrow_set,
1016             flow_state.borrows_in_scope(location),
1017             |this, borrow_index, borrow| match (rw, borrow.kind) {
1018                 // Obviously an activation is compatible with its own
1019                 // reservation (or even prior activating uses of same
1020                 // borrow); so don't check if they interfere.
1021                 //
1022                 // NOTE: *reservations* do conflict with themselves;
1023                 // thus aren't injecting unsoundenss w/ this check.)
1024                 (Activation(_, activating), _) if activating == borrow_index => {
1025                     debug!(
1026                         "check_access_for_conflict place_span: {:?} sd: {:?} rw: {:?} \
1027                          skipping {:?} b/c activation of same borrow_index",
1028                         place_span,
1029                         sd,
1030                         rw,
1031                         (borrow_index, borrow),
1032                     );
1033                     Control::Continue
1034                 }
1035
1036                 (Read(_), BorrowKind::Shared) | (Reservation(..), BorrowKind::Shared) => {
1037                     Control::Continue
1038                 }
1039
1040                 (Read(kind), BorrowKind::Unique) | (Read(kind), BorrowKind::Mut { .. }) => {
1041                     // Reading from mere reservations of mutable-borrows is OK.
1042                     if !is_active(&this.dominators, borrow, context.loc) {
1043                         assert!(allow_two_phase_borrow(&this.tcx, borrow.kind));
1044                         return Control::Continue;
1045                     }
1046
1047                     match kind {
1048                         ReadKind::Copy => {
1049                             error_reported = true;
1050                             this.report_use_while_mutably_borrowed(context, place_span, borrow)
1051                         }
1052                         ReadKind::Borrow(bk) => {
1053                             error_reported = true;
1054                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1055                         }
1056                     }
1057                     Control::Break
1058                 }
1059
1060                 (Reservation(kind), BorrowKind::Unique)
1061                 | (Reservation(kind), BorrowKind::Mut { .. })
1062                 | (Activation(kind, _), _)
1063                 | (Write(kind), _) => {
1064                     match rw {
1065                         Reservation(_) => {
1066                             debug!(
1067                                 "recording invalid reservation of \
1068                                  place: {:?}",
1069                                 place_span.0
1070                             );
1071                             this.reservation_error_reported.insert(place_span.0.clone());
1072                         }
1073                         Activation(_, activating) => {
1074                             debug!(
1075                                 "observing check_place for activation of \
1076                                  borrow_index: {:?}",
1077                                 activating
1078                             );
1079                         }
1080                         Read(..) | Write(..) => {}
1081                     }
1082
1083                     match kind {
1084                         WriteKind::MutableBorrow(bk) => {
1085                             error_reported = true;
1086                             this.report_conflicting_borrow(context, place_span, bk, &borrow)
1087                         }
1088                         WriteKind::StorageDeadOrDrop => {
1089                             error_reported = true;
1090                             this.report_borrowed_value_does_not_live_long_enough(
1091                                 context,
1092                                 borrow,
1093                                 place_span,
1094                                 Some(kind),
1095                             );
1096                         }
1097                         WriteKind::Mutate => {
1098                             error_reported = true;
1099                             this.report_illegal_mutation_of_borrowed(context, place_span, borrow)
1100                         }
1101                         WriteKind::Move => {
1102                             error_reported = true;
1103                             this.report_move_out_while_borrowed(context, place_span, &borrow)
1104                         }
1105                     }
1106                     Control::Break
1107                 }
1108             },
1109         );
1110
1111         error_reported
1112     }
1113
1114     fn mutate_place(
1115         &mut self,
1116         context: Context,
1117         place_span: (&Place<'tcx>, Span),
1118         kind: ShallowOrDeep,
1119         mode: MutateMode,
1120         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1121     ) {
1122         // Write of P[i] or *P, or WriteAndRead of any P, requires P init'd.
1123         match mode {
1124             MutateMode::WriteAndRead => {
1125                 self.check_if_path_or_subpath_is_moved(
1126                     context,
1127                     InitializationRequiringAction::Update,
1128                     place_span,
1129                     flow_state,
1130                 );
1131             }
1132             MutateMode::JustWrite => {
1133                 self.check_if_assigned_path_is_moved(context, place_span, flow_state);
1134             }
1135         }
1136
1137         let errors_reported = self.access_place(
1138             context,
1139             place_span,
1140             (kind, Write(WriteKind::Mutate)),
1141             // We want immutable upvars to cause an "assignment to immutable var"
1142             // error, not an "reassignment of immutable var" error, because the
1143             // latter can't find a good previous assignment span.
1144             //
1145             // There's probably a better way to do this.
1146             LocalMutationIsAllowed::ExceptUpvars,
1147             flow_state,
1148         );
1149
1150         if !errors_reported.mutability_error {
1151             // check for reassignments to immutable local variables
1152             self.check_if_reassignment_to_immutable_state(context, place_span, flow_state);
1153         }
1154     }
1155
1156     fn consume_rvalue(
1157         &mut self,
1158         context: Context,
1159         (rvalue, span): (&Rvalue<'tcx>, Span),
1160         _location: Location,
1161         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1162     ) {
1163         match *rvalue {
1164             Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
1165                 let access_kind = match bk {
1166                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
1167                     BorrowKind::Unique | BorrowKind::Mut { .. } => {
1168                         let wk = WriteKind::MutableBorrow(bk);
1169                         if allow_two_phase_borrow(&self.tcx, bk) {
1170                             (Deep, Reservation(wk))
1171                         } else {
1172                             (Deep, Write(wk))
1173                         }
1174                     }
1175                 };
1176
1177                 self.access_place(
1178                     context,
1179                     (place, span),
1180                     access_kind,
1181                     LocalMutationIsAllowed::No,
1182                     flow_state,
1183                 );
1184
1185                 self.check_if_path_or_subpath_is_moved(
1186                     context,
1187                     InitializationRequiringAction::Borrow,
1188                     (place, span),
1189                     flow_state,
1190                 );
1191             }
1192
1193             Rvalue::Use(ref operand)
1194             | Rvalue::Repeat(ref operand, _)
1195             | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
1196             | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
1197                 self.consume_operand(context, (operand, span), flow_state)
1198             }
1199
1200             Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
1201                 let af = match *rvalue {
1202                     Rvalue::Len(..) => ArtificialField::ArrayLength,
1203                     Rvalue::Discriminant(..) => ArtificialField::Discriminant,
1204                     _ => unreachable!(),
1205                 };
1206                 self.access_place(
1207                     context,
1208                     (place, span),
1209                     (Shallow(Some(af)), Read(ReadKind::Copy)),
1210                     LocalMutationIsAllowed::No,
1211                     flow_state,
1212                 );
1213                 self.check_if_path_or_subpath_is_moved(
1214                     context,
1215                     InitializationRequiringAction::Use,
1216                     (place, span),
1217                     flow_state,
1218                 );
1219             }
1220
1221             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
1222             | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
1223                 self.consume_operand(context, (operand1, span), flow_state);
1224                 self.consume_operand(context, (operand2, span), flow_state);
1225             }
1226
1227             Rvalue::NullaryOp(_op, _ty) => {
1228                 // nullary ops take no dynamic input; no borrowck effect.
1229                 //
1230                 // FIXME: is above actually true? Do we want to track
1231                 // the fact that uninitialized data can be created via
1232                 // `NullOp::Box`?
1233             }
1234
1235             Rvalue::Aggregate(ref aggregate_kind, ref operands) => {
1236                 // We need to report back the list of mutable upvars that were
1237                 // moved into the closure and subsequently used by the closure,
1238                 // in order to populate our used_mut set.
1239                 match **aggregate_kind {
1240                     AggregateKind::Closure(def_id, _)
1241                     | AggregateKind::Generator(def_id, _, _) => {
1242                         let BorrowCheckResult {
1243                             used_mut_upvars, ..
1244                         } = self.tcx.mir_borrowck(def_id);
1245                         debug!("{:?} used_mut_upvars={:?}", def_id, used_mut_upvars);
1246                         for field in used_mut_upvars {
1247                             // This relies on the current way that by-value
1248                             // captures of a closure are copied/moved directly
1249                             // when generating MIR.
1250                             match operands[field.index()] {
1251                                 Operand::Move(Place::Local(local))
1252                                 | Operand::Copy(Place::Local(local)) => {
1253                                     self.used_mut.insert(local);
1254                                 }
1255                                 Operand::Move(ref place @ Place::Projection(_))
1256                                 | Operand::Copy(ref place @ Place::Projection(_)) => {
1257                                     if let Some(field) = place.is_upvar_field_projection(
1258                                             self.mir, &self.tcx) {
1259                                         self.used_mut_upvars.push(field);
1260                                     }
1261                                 }
1262                                 Operand::Move(Place::Static(..))
1263                                 | Operand::Copy(Place::Static(..))
1264                                 | Operand::Move(Place::Promoted(..))
1265                                 | Operand::Copy(Place::Promoted(..))
1266                                 | Operand::Constant(..) => {}
1267                             }
1268                         }
1269                     }
1270                     AggregateKind::Adt(..)
1271                     | AggregateKind::Array(..)
1272                     | AggregateKind::Tuple { .. } => (),
1273                 }
1274
1275                 for operand in operands {
1276                     self.consume_operand(context, (operand, span), flow_state);
1277                 }
1278             }
1279         }
1280     }
1281
1282     fn consume_operand(
1283         &mut self,
1284         context: Context,
1285         (operand, span): (&Operand<'tcx>, Span),
1286         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1287     ) {
1288         match *operand {
1289             Operand::Copy(ref place) => {
1290                 // copy of place: check if this is "copy of frozen path"
1291                 // (FIXME: see check_loans.rs)
1292                 self.access_place(
1293                     context,
1294                     (place, span),
1295                     (Deep, Read(ReadKind::Copy)),
1296                     LocalMutationIsAllowed::No,
1297                     flow_state,
1298                 );
1299
1300                 // Finally, check if path was already moved.
1301                 self.check_if_path_or_subpath_is_moved(
1302                     context,
1303                     InitializationRequiringAction::Use,
1304                     (place, span),
1305                     flow_state,
1306                 );
1307             }
1308             Operand::Move(ref place) => {
1309                 // move of place: check if this is move of already borrowed path
1310                 self.access_place(
1311                     context,
1312                     (place, span),
1313                     (Deep, Write(WriteKind::Move)),
1314                     LocalMutationIsAllowed::Yes,
1315                     flow_state,
1316                 );
1317
1318                 // Finally, check if path was already moved.
1319                 self.check_if_path_or_subpath_is_moved(
1320                     context,
1321                     InitializationRequiringAction::Use,
1322                     (place, span),
1323                     flow_state,
1324                 );
1325             }
1326             Operand::Constant(_) => {}
1327         }
1328     }
1329
1330     /// Returns whether a borrow of this place is invalidated when the function
1331     /// exits
1332     fn check_for_invalidation_at_exit(
1333         &mut self,
1334         context: Context,
1335         borrow: &BorrowData<'tcx>,
1336         span: Span,
1337     ) {
1338         debug!("check_for_invalidation_at_exit({:?})", borrow);
1339         let place = &borrow.borrowed_place;
1340         let root_place = self.prefixes(place, PrefixSet::All).last().unwrap();
1341
1342         // FIXME(nll-rfc#40): do more precise destructor tracking here. For now
1343         // we just know that all locals are dropped at function exit (otherwise
1344         // we'll have a memory leak) and assume that all statics have a destructor.
1345         //
1346         // FIXME: allow thread-locals to borrow other thread locals?
1347         let (might_be_alive, will_be_dropped) = match root_place {
1348             Place::Promoted(_) => (true, false),
1349             Place::Static(statik) => {
1350                 // Thread-locals might be dropped after the function exits, but
1351                 // "true" statics will never be.
1352                 let is_thread_local = self
1353                     .tcx
1354                     .get_attrs(statik.def_id)
1355                     .iter()
1356                     .any(|attr| attr.check_name("thread_local"));
1357
1358                 (true, is_thread_local)
1359             }
1360             Place::Local(_) => {
1361                 // Locals are always dropped at function exit, and if they
1362                 // have a destructor it would've been called already.
1363                 (false, self.locals_are_invalidated_at_exit)
1364             }
1365             Place::Projection(..) => {
1366                 bug!("root of {:?} is a projection ({:?})?", place, root_place)
1367             }
1368         };
1369
1370         if !will_be_dropped {
1371             debug!(
1372                 "place_is_invalidated_at_exit({:?}) - won't be dropped",
1373                 place
1374             );
1375             return;
1376         }
1377
1378         // FIXME: replace this with a proper borrow_conflicts_with_place when
1379         // that is merged.
1380         let sd = if might_be_alive { Deep } else { Shallow(None) };
1381
1382         if places_conflict::places_conflict(self.tcx, self.mir, place, root_place, sd) {
1383             debug!("check_for_invalidation_at_exit({:?}): INVALID", place);
1384             // FIXME: should be talking about the region lifetime instead
1385             // of just a span here.
1386             let span = self.tcx.sess.codemap().end_point(span);
1387             self.report_borrowed_value_does_not_live_long_enough(
1388                 context,
1389                 borrow,
1390                 (place, span),
1391                 None,
1392             )
1393         }
1394     }
1395
1396     /// Reports an error if this is a borrow of local data.
1397     /// This is called for all Yield statements on movable generators
1398     fn check_for_local_borrow(&mut self, borrow: &BorrowData<'tcx>, yield_span: Span) {
1399         debug!("check_for_local_borrow({:?})", borrow);
1400
1401         if borrow_of_local_data(&borrow.borrowed_place) {
1402             let err = self.tcx
1403                 .cannot_borrow_across_generator_yield(
1404                     self.retrieve_borrow_span(borrow),
1405                     yield_span,
1406                     Origin::Mir,
1407                 );
1408
1409             err.buffer(&mut self.errors_buffer);
1410         }
1411     }
1412
1413     fn check_activations(
1414         &mut self,
1415         location: Location,
1416         span: Span,
1417         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1418     ) {
1419         if !self.tcx.two_phase_borrows() {
1420             return;
1421         }
1422
1423         // Two-phase borrow support: For each activation that is newly
1424         // generated at this statement, check if it interferes with
1425         // another borrow.
1426         let borrow_set = self.borrow_set.clone();
1427         for &borrow_index in borrow_set.activations_at_location(location) {
1428             let borrow = &borrow_set[borrow_index];
1429
1430             // only mutable borrows should be 2-phase
1431             assert!(match borrow.kind {
1432                 BorrowKind::Shared => false,
1433                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
1434             });
1435
1436             self.access_place(
1437                 ContextKind::Activation.new(location),
1438                 (&borrow.borrowed_place, span),
1439                 (
1440                     Deep,
1441                     Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
1442                 ),
1443                 LocalMutationIsAllowed::No,
1444                 flow_state,
1445             );
1446             // We do not need to call `check_if_path_or_subpath_is_moved`
1447             // again, as we already called it when we made the
1448             // initial reservation.
1449         }
1450     }
1451 }
1452
1453 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
1454     fn check_if_reassignment_to_immutable_state(
1455         &mut self,
1456         context: Context,
1457         (place, span): (&Place<'tcx>, Span),
1458         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1459     ) {
1460         debug!("check_if_reassignment_to_immutable_state({:?})", place);
1461         // determine if this path has a non-mut owner (and thus needs checking).
1462         let err_place = match self.is_mutable(place, LocalMutationIsAllowed::No) {
1463             Ok(..) => return,
1464             Err(place) => place,
1465         };
1466         debug!(
1467             "check_if_reassignment_to_immutable_state({:?}) - is an imm local",
1468             place
1469         );
1470
1471         for i in flow_state.ever_inits.iter_incoming() {
1472             let init = self.move_data.inits[i];
1473             let init_place = &self.move_data.move_paths[init.path].place;
1474             if places_conflict::places_conflict(self.tcx, self.mir, &init_place, place, Deep) {
1475                 self.report_illegal_reassignment(context, (place, span), init.span, err_place);
1476                 break;
1477             }
1478         }
1479     }
1480
1481     fn check_if_full_path_is_moved(
1482         &mut self,
1483         context: Context,
1484         desired_action: InitializationRequiringAction,
1485         place_span: (&Place<'tcx>, Span),
1486         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1487     ) {
1488         // FIXME: analogous code in check_loans first maps `place` to
1489         // its base_path ... but is that what we want here?
1490         let place = self.base_path(place_span.0);
1491
1492         let maybe_uninits = &flow_state.uninits;
1493         let curr_move_outs = &flow_state.move_outs;
1494
1495         // Bad scenarios:
1496         //
1497         // 1. Move of `a.b.c`, use of `a.b.c`
1498         // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
1499         // 3. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
1500         //    partial initialization support, one might have `a.x`
1501         //    initialized but not `a.b`.
1502         //
1503         // OK scenarios:
1504         //
1505         // 4. Move of `a.b.c`, use of `a.b.d`
1506         // 5. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1507         // 6. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1508         //    must have been initialized for the use to be sound.
1509         // 7. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1510
1511         // The dataflow tracks shallow prefixes distinctly (that is,
1512         // field-accesses on P distinctly from P itself), in order to
1513         // track substructure initialization separately from the whole
1514         // structure.
1515         //
1516         // E.g., when looking at (*a.b.c).d, if the closest prefix for
1517         // which we have a MovePath is `a.b`, then that means that the
1518         // initialization state of `a.b` is all we need to inspect to
1519         // know if `a.b.c` is valid (and from that we infer that the
1520         // dereference and `.d` access is also valid, since we assume
1521         // `a.b.c` is assigned a reference to a initialized and
1522         // well-formed record structure.)
1523
1524         // Therefore, if we seek out the *closest* prefix for which we
1525         // have a MovePath, that should capture the initialization
1526         // state for the place scenario.
1527         //
1528         // This code covers scenarios 1, 2, and 3.
1529
1530         debug!("check_if_full_path_is_moved place: {:?}", place);
1531         match self.move_path_closest_to(place) {
1532             Ok(mpi) => {
1533                 if maybe_uninits.contains(&mpi) {
1534                     self.report_use_of_moved_or_uninitialized(
1535                         context,
1536                         desired_action,
1537                         place_span,
1538                         mpi,
1539                         curr_move_outs,
1540                     );
1541                     return; // don't bother finding other problems.
1542                 }
1543             }
1544             Err(NoMovePathFound::ReachedStatic) => {
1545                 // Okay: we do not build MoveData for static variables
1546             } // Only query longest prefix with a MovePath, not further
1547               // ancestors; dataflow recurs on children when parents
1548               // move (to support partial (re)inits).
1549               //
1550               // (I.e. querying parents breaks scenario 7; but may want
1551               // to do such a query based on partial-init feature-gate.)
1552         }
1553     }
1554
1555     fn check_if_path_or_subpath_is_moved(
1556         &mut self,
1557         context: Context,
1558         desired_action: InitializationRequiringAction,
1559         place_span: (&Place<'tcx>, Span),
1560         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1561     ) {
1562         // FIXME: analogous code in check_loans first maps `place` to
1563         // its base_path ... but is that what we want here?
1564         let place = self.base_path(place_span.0);
1565
1566         let maybe_uninits = &flow_state.uninits;
1567         let curr_move_outs = &flow_state.move_outs;
1568
1569         // Bad scenarios:
1570         //
1571         // 1. Move of `a.b.c`, use of `a` or `a.b`
1572         //    partial initialization support, one might have `a.x`
1573         //    initialized but not `a.b`.
1574         // 2. All bad scenarios from `check_if_full_path_is_moved`
1575         //
1576         // OK scenarios:
1577         //
1578         // 3. Move of `a.b.c`, use of `a.b.d`
1579         // 4. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1580         // 5. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1581         //    must have been initialized for the use to be sound.
1582         // 6. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1583
1584         self.check_if_full_path_is_moved(context, desired_action, place_span, flow_state);
1585
1586         // A move of any shallow suffix of `place` also interferes
1587         // with an attempt to use `place`. This is scenario 3 above.
1588         //
1589         // (Distinct from handling of scenarios 1+2+4 above because
1590         // `place` does not interfere with suffixes of its prefixes,
1591         // e.g. `a.b.c` does not interfere with `a.b.d`)
1592         //
1593         // This code covers scenario 1.
1594
1595         debug!("check_if_path_or_subpath_is_moved place: {:?}", place);
1596         if let Some(mpi) = self.move_path_for_place(place) {
1597             if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) {
1598                 self.report_use_of_moved_or_uninitialized(
1599                     context,
1600                     desired_action,
1601                     place_span,
1602                     child_mpi,
1603                     curr_move_outs,
1604                 );
1605                 return; // don't bother finding other problems.
1606             }
1607         }
1608     }
1609
1610     /// Currently MoveData does not store entries for all places in
1611     /// the input MIR. For example it will currently filter out
1612     /// places that are Copy; thus we do not track places of shared
1613     /// reference type. This routine will walk up a place along its
1614     /// prefixes, searching for a foundational place that *is*
1615     /// tracked in the MoveData.
1616     ///
1617     /// An Err result includes a tag indicated why the search failed.
1618     /// Currently this can only occur if the place is built off of a
1619     /// static variable, as we do not track those in the MoveData.
1620     fn move_path_closest_to(
1621         &mut self,
1622         place: &Place<'tcx>,
1623     ) -> Result<MovePathIndex, NoMovePathFound> {
1624         let mut last_prefix = place;
1625         for prefix in self.prefixes(place, PrefixSet::All) {
1626             if let Some(mpi) = self.move_path_for_place(prefix) {
1627                 return Ok(mpi);
1628             }
1629             last_prefix = prefix;
1630         }
1631         match *last_prefix {
1632             Place::Local(_) => panic!("should have move path for every Local"),
1633             Place::Projection(_) => panic!("PrefixSet::All meant don't stop for Projection"),
1634             Place::Promoted(_) |
1635             Place::Static(_) => return Err(NoMovePathFound::ReachedStatic),
1636         }
1637     }
1638
1639     fn move_path_for_place(&mut self, place: &Place<'tcx>) -> Option<MovePathIndex> {
1640         // If returns None, then there is no move path corresponding
1641         // to a direct owner of `place` (which means there is nothing
1642         // that borrowck tracks for its analysis).
1643
1644         match self.move_data.rev_lookup.find(place) {
1645             LookupResult::Parent(_) => None,
1646             LookupResult::Exact(mpi) => Some(mpi),
1647         }
1648     }
1649
1650     fn check_if_assigned_path_is_moved(
1651         &mut self,
1652         context: Context,
1653         (place, span): (&Place<'tcx>, Span),
1654         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1655     ) {
1656         debug!("check_if_assigned_path_is_moved place: {:?}", place);
1657         // recur down place; dispatch to external checks when necessary
1658         let mut place = place;
1659         loop {
1660             match *place {
1661                 Place::Promoted(_) |
1662                 Place::Local(_) | Place::Static(_) => {
1663                     // assigning to `x` does not require `x` be initialized.
1664                     break;
1665                 }
1666                 Place::Projection(ref proj) => {
1667                     let Projection { ref base, ref elem } = **proj;
1668                     match *elem {
1669                         ProjectionElem::Index(_/*operand*/) |
1670                         ProjectionElem::ConstantIndex { .. } |
1671                         // assigning to P[i] requires P to be valid.
1672                         ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
1673                         // assigning to (P->variant) is okay if assigning to `P` is okay
1674                         //
1675                         // FIXME: is this true even if P is a adt with a dtor?
1676                         { }
1677
1678                         // assigning to (*P) requires P to be initialized
1679                         ProjectionElem::Deref => {
1680                             self.check_if_full_path_is_moved(
1681                                 context, InitializationRequiringAction::Use,
1682                                 (base, span), flow_state);
1683                             // (base initialized; no need to
1684                             // recur further)
1685                             break;
1686                         }
1687
1688                         ProjectionElem::Subslice { .. } => {
1689                             panic!("we don't allow assignments to subslices, context: {:?}",
1690                                    context);
1691                         }
1692
1693                         ProjectionElem::Field(..) => {
1694                             // if type of `P` has a dtor, then
1695                             // assigning to `P.f` requires `P` itself
1696                             // be already initialized
1697                             let tcx = self.tcx;
1698                             match base.ty(self.mir, tcx).to_ty(tcx).sty {
1699                                 ty::TyAdt(def, _) if def.has_dtor(tcx) => {
1700
1701                                     // FIXME: analogous code in
1702                                     // check_loans.rs first maps
1703                                     // `base` to its base_path.
1704
1705                                     self.check_if_path_or_subpath_is_moved(
1706                                         context, InitializationRequiringAction::Assignment,
1707                                         (base, span), flow_state);
1708
1709                                     // (base initialized; no need to
1710                                     // recur further)
1711                                     break;
1712                                 }
1713                                 _ => {}
1714                             }
1715                         }
1716                     }
1717
1718                     place = base;
1719                     continue;
1720                 }
1721             }
1722         }
1723     }
1724
1725
1726     /// Check the permissions for the given place and read or write kind
1727     ///
1728     /// Returns true if an error is reported, false otherwise.
1729     fn check_access_permissions(
1730         &mut self,
1731         (place, span): (&Place<'tcx>, Span),
1732         kind: ReadOrWrite,
1733         is_local_mutation_allowed: LocalMutationIsAllowed,
1734         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1735         location: Location,
1736     ) -> bool {
1737         debug!(
1738             "check_access_permissions({:?}, {:?}, {:?})",
1739             place, kind, is_local_mutation_allowed
1740         );
1741
1742         let error_access;
1743         let the_place_err;
1744
1745         match kind {
1746             Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1747             | Reservation(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. }))
1748             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Unique))
1749             | Write(WriteKind::MutableBorrow(borrow_kind @ BorrowKind::Mut { .. })) => {
1750                 let is_local_mutation_allowed = match borrow_kind {
1751                     BorrowKind::Unique => LocalMutationIsAllowed::Yes,
1752                     BorrowKind::Mut { .. } => is_local_mutation_allowed,
1753                     BorrowKind::Shared => unreachable!(),
1754                 };
1755                 match self.is_mutable(place, is_local_mutation_allowed) {
1756                     Ok(root_place) => {
1757                         self.add_used_mut(root_place, flow_state);
1758                         return false;
1759                     }
1760                     Err(place_err) => {
1761                         error_access = AccessKind::MutableBorrow;
1762                         the_place_err = place_err;
1763                     }
1764                 }
1765             }
1766             Reservation(WriteKind::Mutate) | Write(WriteKind::Mutate) => {
1767                 match self.is_mutable(place, is_local_mutation_allowed) {
1768                     Ok(root_place) => {
1769                         self.add_used_mut(root_place, flow_state);
1770                         return false;
1771                     }
1772                     Err(place_err) => {
1773                         error_access = AccessKind::Mutate;
1774                         the_place_err = place_err;
1775                     }
1776                 }
1777             }
1778
1779             Reservation(wk @ WriteKind::Move)
1780             | Write(wk @ WriteKind::Move)
1781             | Reservation(wk @ WriteKind::StorageDeadOrDrop)
1782             | Reservation(wk @ WriteKind::MutableBorrow(BorrowKind::Shared))
1783             | Write(wk @ WriteKind::StorageDeadOrDrop)
1784             | Write(wk @ WriteKind::MutableBorrow(BorrowKind::Shared)) => {
1785                 if let Err(_place_err) = self.is_mutable(place, is_local_mutation_allowed) {
1786                     if self.tcx.migrate_borrowck() {
1787                         // rust-lang/rust#46908: In pure NLL mode this
1788                         // code path should be unreachable (and thus
1789                         // we signal an ICE in the else branch
1790                         // here). But we can legitimately get here
1791                         // under borrowck=migrate mode, so instead of
1792                         // ICE'ing we instead report a legitimate
1793                         // error (which will then be downgraded to a
1794                         // warning by the migrate machinery).
1795                         error_access = match wk {
1796                             WriteKind::MutableBorrow(_) => AccessKind::MutableBorrow,
1797                             WriteKind::Move => AccessKind::Move,
1798                             WriteKind::StorageDeadOrDrop |
1799                             WriteKind::Mutate => AccessKind::Mutate,
1800                         };
1801                         self.report_mutability_error(
1802                             place,
1803                             span,
1804                             _place_err,
1805                             error_access,
1806                             location,
1807                         );
1808                     } else {
1809                         self.tcx.sess.delay_span_bug(
1810                             span,
1811                             &format!(
1812                                 "Accessing `{:?}` with the kind `{:?}` shouldn't be possible",
1813                                 place, kind
1814                             ),
1815                         );
1816                     }
1817                 }
1818                 return false;
1819             }
1820             Activation(..) => {
1821                 // permission checks are done at Reservation point.
1822                 return false;
1823             }
1824             Read(ReadKind::Borrow(BorrowKind::Unique))
1825             | Read(ReadKind::Borrow(BorrowKind::Mut { .. }))
1826             | Read(ReadKind::Borrow(BorrowKind::Shared))
1827             | Read(ReadKind::Copy) => {
1828                 // Access authorized
1829                 return false;
1830             }
1831         }
1832
1833         // at this point, we have set up the error reporting state.
1834         self.report_mutability_error(
1835             place,
1836             span,
1837             the_place_err,
1838             error_access,
1839             location,
1840         );
1841         return true;
1842     }
1843
1844     /// Adds the place into the used mutable variables set
1845     fn add_used_mut<'d>(
1846         &mut self,
1847         root_place: RootPlace<'d, 'tcx>,
1848         flow_state: &Flows<'cx, 'gcx, 'tcx>,
1849     ) {
1850         match root_place {
1851             RootPlace {
1852                 place: Place::Local(local),
1853                 is_local_mutation_allowed,
1854             } => {
1855                 if is_local_mutation_allowed != LocalMutationIsAllowed::Yes {
1856                     // If the local may be initialized, and it is now currently being
1857                     // mutated, then it is justified to be annotated with the `mut`
1858                     // keyword, since the mutation may be a possible reassignment.
1859                     let mpi = self.move_data.rev_lookup.find_local(*local);
1860                     let ii = &self.move_data.init_path_map[mpi];
1861                     for index in ii {
1862                         if flow_state.ever_inits.contains(index) {
1863                             self.used_mut.insert(*local);
1864                             break;
1865                         }
1866                     }
1867                 }
1868             }
1869             RootPlace {
1870                 place: _,
1871                 is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1872             } => {}
1873             RootPlace {
1874                 place: place @ Place::Projection(_),
1875                 is_local_mutation_allowed: _,
1876             } => {
1877                 if let Some(field) = place.is_upvar_field_projection(self.mir, &self.tcx) {
1878                     self.used_mut_upvars.push(field);
1879                 }
1880             }
1881             RootPlace {
1882                 place: Place::Promoted(..),
1883                 is_local_mutation_allowed: _,
1884             } => {}
1885             RootPlace {
1886                 place: Place::Static(..),
1887                 is_local_mutation_allowed: _,
1888             } => {}
1889         }
1890     }
1891
1892     /// Whether this value be written or borrowed mutably.
1893     /// Returns the root place if the place passed in is a projection.
1894     fn is_mutable<'d>(
1895         &self,
1896         place: &'d Place<'tcx>,
1897         is_local_mutation_allowed: LocalMutationIsAllowed,
1898     ) -> Result<RootPlace<'d, 'tcx>, &'d Place<'tcx>> {
1899         match *place {
1900             Place::Local(local) => {
1901                 let local = &self.mir.local_decls[local];
1902                 match local.mutability {
1903                     Mutability::Not => match is_local_mutation_allowed {
1904                         LocalMutationIsAllowed::Yes => Ok(RootPlace {
1905                             place,
1906                             is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
1907                         }),
1908                         LocalMutationIsAllowed::ExceptUpvars => Ok(RootPlace {
1909                             place,
1910                             is_local_mutation_allowed: LocalMutationIsAllowed::ExceptUpvars,
1911                         }),
1912                         LocalMutationIsAllowed::No => Err(place),
1913                     },
1914                     Mutability::Mut => Ok(RootPlace {
1915                         place,
1916                         is_local_mutation_allowed,
1917                     }),
1918                 }
1919             }
1920             // The rules for promotion are made by `qualify_consts`, there wouldn't even be a
1921             // `Place::Promoted` if the promotion weren't 100% legal. So we just forward this
1922             Place::Promoted(_) => Ok(RootPlace {
1923                 place,
1924                 is_local_mutation_allowed,
1925             }),
1926             Place::Static(ref static_) => {
1927                 if self.tcx.is_static(static_.def_id) != Some(hir::Mutability::MutMutable) {
1928                     Err(place)
1929                 } else {
1930                     Ok(RootPlace {
1931                         place,
1932                         is_local_mutation_allowed,
1933                     })
1934                 }
1935             }
1936             Place::Projection(ref proj) => {
1937                 match proj.elem {
1938                     ProjectionElem::Deref => {
1939                         let base_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
1940
1941                         // Check the kind of deref to decide
1942                         match base_ty.sty {
1943                             ty::TyRef(_, _, mutbl) => {
1944                                 match mutbl {
1945                                     // Shared borrowed data is never mutable
1946                                     hir::MutImmutable => Err(place),
1947                                     // Mutably borrowed data is mutable, but only if we have a
1948                                     // unique path to the `&mut`
1949                                     hir::MutMutable => {
1950                                         let mode = match place.is_upvar_field_projection(
1951                                             self.mir, &self.tcx)
1952                                         {
1953                                             Some(field)
1954                                                 if {
1955                                                     self.mir.upvar_decls[field.index()].by_ref
1956                                                 } =>
1957                                             {
1958                                                 is_local_mutation_allowed
1959                                             }
1960                                             _ => LocalMutationIsAllowed::Yes,
1961                                         };
1962
1963                                         self.is_mutable(&proj.base, mode)
1964                                     }
1965                                 }
1966                             }
1967                             ty::TyRawPtr(tnm) => {
1968                                 match tnm.mutbl {
1969                                     // `*const` raw pointers are not mutable
1970                                     hir::MutImmutable => return Err(place),
1971                                     // `*mut` raw pointers are always mutable, regardless of
1972                                     // context. The users have to check by themselves.
1973                                     hir::MutMutable => {
1974                                         return Ok(RootPlace {
1975                                             place,
1976                                             is_local_mutation_allowed,
1977                                         });
1978                                     }
1979                                 }
1980                             }
1981                             // `Box<T>` owns its content, so mutable if its location is mutable
1982                             _ if base_ty.is_box() => {
1983                                 self.is_mutable(&proj.base, is_local_mutation_allowed)
1984                             }
1985                             // Deref should only be for reference, pointers or boxes
1986                             _ => bug!("Deref of unexpected type: {:?}", base_ty),
1987                         }
1988                     }
1989                     // All other projections are owned by their base path, so mutable if
1990                     // base path is mutable
1991                     ProjectionElem::Field(..)
1992                     | ProjectionElem::Index(..)
1993                     | ProjectionElem::ConstantIndex { .. }
1994                     | ProjectionElem::Subslice { .. }
1995                     | ProjectionElem::Downcast(..) => {
1996                         let upvar_field_projection = place.is_upvar_field_projection(
1997                             self.mir, &self.tcx);
1998                         if let Some(field) = upvar_field_projection {
1999                             let decl = &self.mir.upvar_decls[field.index()];
2000                             debug!(
2001                                 "decl.mutability={:?} local_mutation_is_allowed={:?} place={:?}",
2002                                 decl, is_local_mutation_allowed, place
2003                             );
2004                             match (decl.mutability, is_local_mutation_allowed) {
2005                                 (Mutability::Not, LocalMutationIsAllowed::No)
2006                                 | (Mutability::Not, LocalMutationIsAllowed::ExceptUpvars) => {
2007                                     Err(place)
2008                                 }
2009                                 (Mutability::Not, LocalMutationIsAllowed::Yes)
2010                                 | (Mutability::Mut, _) => {
2011                                     // Subtle: this is an upvar
2012                                     // reference, so it looks like
2013                                     // `self.foo` -- we want to double
2014                                     // check that the context `*self`
2015                                     // is mutable (i.e., this is not a
2016                                     // `Fn` closure).  But if that
2017                                     // check succeeds, we want to
2018                                     // *blame* the mutability on
2019                                     // `place` (that is,
2020                                     // `self.foo`). This is used to
2021                                     // propagate the info about
2022                                     // whether mutability declarations
2023                                     // are used outwards, so that we register
2024                                     // the outer variable as mutable. Otherwise a
2025                                     // test like this fails to record the `mut`
2026                                     // as needed:
2027                                     //
2028                                     // ```
2029                                     // fn foo<F: FnOnce()>(_f: F) { }
2030                                     // fn main() {
2031                                     //     let var = Vec::new();
2032                                     //     foo(move || {
2033                                     //         var.push(1);
2034                                     //     });
2035                                     // }
2036                                     // ```
2037                                     let _ = self.is_mutable(&proj.base, is_local_mutation_allowed)?;
2038                                     Ok(RootPlace {
2039                                         place,
2040                                         is_local_mutation_allowed,
2041                                     })
2042                                 }
2043                             }
2044                         } else {
2045                             self.is_mutable(&proj.base, is_local_mutation_allowed)
2046                         }
2047                     }
2048                 }
2049             }
2050         }
2051     }
2052 }
2053
2054 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2055 enum NoMovePathFound {
2056     ReachedStatic,
2057 }
2058
2059 /// The degree of overlap between 2 places for borrow-checking.
2060 enum Overlap {
2061     /// The places might partially overlap - in this case, we give
2062     /// up and say that they might conflict. This occurs when
2063     /// different fields of a union are borrowed. For example,
2064     /// if `u` is a union, we have no way of telling how disjoint
2065     /// `u.a.x` and `a.b.y` are.
2066     Arbitrary,
2067     /// The places have the same type, and are either completely disjoint
2068     /// or equal - i.e. they can't "partially" overlap as can occur with
2069     /// unions. This is the "base case" on which we recur for extensions
2070     /// of the place.
2071     EqualOrDisjoint,
2072     /// The places are disjoint, so we know all extensions of them
2073     /// will also be disjoint.
2074     Disjoint,
2075 }
2076
2077 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
2078     // FIXME (#16118): function intended to allow the borrow checker
2079     // to be less precise in its handling of Box while still allowing
2080     // moves out of a Box. They should be removed when/if we stop
2081     // treating Box specially (e.g. when/if DerefMove is added...)
2082
2083     fn base_path<'d>(&self, place: &'d Place<'tcx>) -> &'d Place<'tcx> {
2084         //! Returns the base of the leftmost (deepest) dereference of an
2085         //! Box in `place`. If there is no dereference of an Box
2086         //! in `place`, then it just returns `place` itself.
2087
2088         let mut cursor = place;
2089         let mut deepest = place;
2090         loop {
2091             let proj = match *cursor {
2092                 Place::Promoted(_) |
2093                 Place::Local(..) | Place::Static(..) => return deepest,
2094                 Place::Projection(ref proj) => proj,
2095             };
2096             if proj.elem == ProjectionElem::Deref
2097                 && place.ty(self.mir, self.tcx).to_ty(self.tcx).is_box()
2098             {
2099                 deepest = &proj.base;
2100             }
2101             cursor = &proj.base;
2102         }
2103     }
2104 }
2105
2106 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2107 struct Context {
2108     kind: ContextKind,
2109     loc: Location,
2110 }
2111
2112 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2113 enum ContextKind {
2114     Activation,
2115     AssignLhs,
2116     AssignRhs,
2117     SetDiscrim,
2118     InlineAsm,
2119     SwitchInt,
2120     Drop,
2121     DropAndReplace,
2122     CallOperator,
2123     CallOperand,
2124     CallDest,
2125     Assert,
2126     Yield,
2127     ReadForMatch,
2128     StorageDead,
2129 }
2130
2131 impl ContextKind {
2132     fn new(self, loc: Location) -> Context {
2133         Context {
2134             kind: self,
2135             loc: loc,
2136         }
2137     }
2138 }