src/librustc_mir/borrow_check/mod.rs

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