src/librustc_mir/borrow_check/mod.rs

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