src/librustc_mir/borrow_check/mod.rs

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