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