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