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