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