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