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