compiler/rustc_borrowck/src/lib.rs

   1 //! This query borrow-checks the MIR to (further) ensure it is not broken.
   2
   3 #![feature(bool_to_option)]
   4 #![feature(box_patterns)]
   5 #![feature(crate_visibility_modifier)]
   6 #![feature(let_else)]
   7 #![feature(min_specialization)]
   8 #![feature(stmt_expr_attributes)]
   9 #![feature(trusted_step)]
  10 #![feature(try_blocks)]
  11 #![recursion_limit = "256"]
  12
  13 #[macro_use]
  14 extern crate rustc_middle;
  15 #[macro_use]
  16 extern crate tracing;
  17
  18 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  19 use rustc_data_structures::graph::dominators::Dominators;
  20 use rustc_errors::{Applicability, Diagnostic, DiagnosticBuilder, ErrorReported};
  21 use rustc_hir as hir;
  22 use rustc_hir::def_id::LocalDefId;
  23 use rustc_hir::Node;
  24 use rustc_index::bit_set::BitSet;
  25 use rustc_index::vec::IndexVec;
  26 use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
  27 use rustc_middle::mir::{
  28     traversal, Body, ClearCrossCrate, Local, Location, Mutability, Operand, Place, PlaceElem,
  29     PlaceRef, VarDebugInfoContents,
  30 };
  31 use rustc_middle::mir::{AggregateKind, BasicBlock, BorrowCheckResult, BorrowKind};
  32 use rustc_middle::mir::{Field, ProjectionElem, Promoted, Rvalue, Statement, StatementKind};
  33 use rustc_middle::mir::{InlineAsmOperand, Terminator, TerminatorKind};
  34 use rustc_middle::ty::query::Providers;
  35 use rustc_middle::ty::{self, CapturedPlace, ParamEnv, RegionVid, TyCtxt};
  36 use rustc_session::lint::builtin::{MUTABLE_BORROW_RESERVATION_CONFLICT, UNUSED_MUT};
  37 use rustc_span::{Span, Symbol, DUMMY_SP};
  38
  39 use either::Either;
  40 use smallvec::SmallVec;
  41 use std::cell::RefCell;
  42 use std::collections::BTreeMap;
  43 use std::mem;
  44 use std::rc::Rc;
  45
  46 use rustc_mir_dataflow::impls::{
  47     EverInitializedPlaces, MaybeInitializedPlaces, MaybeUninitializedPlaces,
  48 };
  49 use rustc_mir_dataflow::move_paths::{InitIndex, MoveOutIndex, MovePathIndex};
  50 use rustc_mir_dataflow::move_paths::{InitLocation, LookupResult, MoveData, MoveError};
  51 use rustc_mir_dataflow::Analysis;
  52 use rustc_mir_dataflow::MoveDataParamEnv;
  53
  54 use self::diagnostics::{AccessKind, RegionName};
  55 use self::location::LocationTable;
  56 use self::prefixes::PrefixSet;
  57 use facts::AllFacts;
  58
  59 use self::path_utils::*;
  60
  61 pub mod borrow_set;
  62 mod borrowck_errors;
  63 mod constraint_generation;
  64 mod constraints;
  65 mod dataflow;
  66 mod def_use;
  67 mod diagnostics;
  68 mod facts;
  69 mod invalidation;
  70 mod location;
  71 mod member_constraints;
  72 mod nll;
  73 mod path_utils;
  74 mod place_ext;
  75 mod places_conflict;
  76 mod prefixes;
  77 mod region_infer;
  78 mod renumber;
  79 mod type_check;
  80 mod universal_regions;
  81 mod used_muts;
  82
  83 // A public API provided for the Rust compiler consumers.
  84 pub mod consumers;
  85
  86 use borrow_set::{BorrowData, BorrowSet};
  87 use dataflow::{BorrowIndex, BorrowckFlowState as Flows, BorrowckResults, Borrows};
  88 use nll::{PoloniusOutput, ToRegionVid};
  89 use place_ext::PlaceExt;
  90 use places_conflict::{places_conflict, PlaceConflictBias};
  91 use region_infer::RegionInferenceContext;
  92
  93 // FIXME(eddyb) perhaps move this somewhere more centrally.
  94 #[derive(Debug)]
  95 struct Upvar<'tcx> {
  96     place: CapturedPlace<'tcx>,
  97
  98     /// If true, the capture is behind a reference.
  99     by_ref: bool,
 100 }
 101
 102 const DEREF_PROJECTION: &[PlaceElem<'_>; 1] = &[ProjectionElem::Deref];
 103
 104 pub fn provide(providers: &mut Providers) {
 105     *providers = Providers {
 106         mir_borrowck: |tcx, did| {
 107             if let Some(def) = ty::WithOptConstParam::try_lookup(did, tcx) {
 108                 tcx.mir_borrowck_const_arg(def)
 109             } else {
 110                 mir_borrowck(tcx, ty::WithOptConstParam::unknown(did))
 111             }
 112         },
 113         mir_borrowck_const_arg: |tcx, (did, param_did)| {
 114             mir_borrowck(tcx, ty::WithOptConstParam { did, const_param_did: Some(param_did) })
 115         },
 116         ..*providers
 117     };
 118 }
 119
 120 fn mir_borrowck<'tcx>(
 121     tcx: TyCtxt<'tcx>,
 122     def: ty::WithOptConstParam<LocalDefId>,
 123 ) -> &'tcx BorrowCheckResult<'tcx> {
 124     let (input_body, promoted) = tcx.mir_promoted(def);
 125     debug!("run query mir_borrowck: {}", tcx.def_path_str(def.did.to_def_id()));
 126
 127     let opt_closure_req = tcx.infer_ctxt().with_opaque_type_inference(def.did).enter(|infcx| {
 128         let input_body: &Body<'_> = &input_body.borrow();
 129         let promoted: &IndexVec<_, _> = &promoted.borrow();
 130         do_mir_borrowck(&infcx, input_body, promoted, false).0
 131     });
 132     debug!("mir_borrowck done");
 133
 134     tcx.arena.alloc(opt_closure_req)
 135 }
 136
 137 /// Perform the actual borrow checking.
 138 ///
 139 /// If `return_body_with_facts` is true, then return the body with non-erased
 140 /// region ids on which the borrow checking was performed together with Polonius
 141 /// facts.
 142 #[instrument(skip(infcx, input_body, input_promoted), level = "debug")]
 143 fn do_mir_borrowck<'a, 'tcx>(
 144     infcx: &InferCtxt<'a, 'tcx>,
 145     input_body: &Body<'tcx>,
 146     input_promoted: &IndexVec<Promoted, Body<'tcx>>,
 147     return_body_with_facts: bool,
 148 ) -> (BorrowCheckResult<'tcx>, Option<Box<BodyWithBorrowckFacts<'tcx>>>) {
 149     let def = input_body.source.with_opt_param().as_local().unwrap();
 150
 151     debug!(?def);
 152
 153     let tcx = infcx.tcx;
 154     let param_env = tcx.param_env(def.did);
 155     let id = tcx.hir().local_def_id_to_hir_id(def.did);
 156
 157     let mut local_names = IndexVec::from_elem(None, &input_body.local_decls);
 158     for var_debug_info in &input_body.var_debug_info {
 159         if let VarDebugInfoContents::Place(place) = var_debug_info.value {
 160             if let Some(local) = place.as_local() {
 161                 if let Some(prev_name) = local_names[local] {
 162                     if var_debug_info.name != prev_name {
 163                         span_bug!(
 164                             var_debug_info.source_info.span,
 165                             "local {:?} has many names (`{}` vs `{}`)",
 166                             local,
 167                             prev_name,
 168                             var_debug_info.name
 169                         );
 170                     }
 171                 }
 172                 local_names[local] = Some(var_debug_info.name);
 173             }
 174         }
 175     }
 176
 177     // Gather the upvars of a closure, if any.
 178     let tables = tcx.typeck_opt_const_arg(def);
 179     if let Some(ErrorReported) = tables.tainted_by_errors {
 180         infcx.set_tainted_by_errors();
 181     }
 182     let upvars: Vec<_> = tables
 183         .closure_min_captures_flattened(def.did.to_def_id())
 184         .map(|captured_place| {
 185             let capture = captured_place.info.capture_kind;
 186             let by_ref = match capture {
 187                 ty::UpvarCapture::ByValue => false,
 188                 ty::UpvarCapture::ByRef(..) => true,
 189             };
 190             Upvar { place: captured_place.clone(), by_ref }
 191         })
 192         .collect();
 193
 194     // Replace all regions with fresh inference variables. This
 195     // requires first making our own copy of the MIR. This copy will
 196     // be modified (in place) to contain non-lexical lifetimes. It
 197     // will have a lifetime tied to the inference context.
 198     let mut body_owned = input_body.clone();
 199     let mut promoted = input_promoted.clone();
 200     let free_regions =
 201         nll::replace_regions_in_mir(infcx, param_env, &mut body_owned, &mut promoted);
 202     let body = &body_owned; // no further changes
 203
 204     let location_table_owned = LocationTable::new(body);
 205     let location_table = &location_table_owned;
 206
 207     let mut errors_buffer = Vec::new();
 208     let (move_data, move_errors): (MoveData<'tcx>, Vec<(Place<'tcx>, MoveError<'tcx>)>) =
 209         match MoveData::gather_moves(&body, tcx, param_env) {
 210             Ok(move_data) => (move_data, Vec::new()),
 211             Err((move_data, move_errors)) => (move_data, move_errors),
 212         };
 213     let promoted_errors = promoted
 214         .iter_enumerated()
 215         .map(|(idx, body)| (idx, MoveData::gather_moves(&body, tcx, param_env)));
 216
 217     let mdpe = MoveDataParamEnv { move_data, param_env };
 218
 219     let mut flow_inits = MaybeInitializedPlaces::new(tcx, &body, &mdpe)
 220         .into_engine(tcx, &body)
 221         .pass_name("borrowck")
 222         .iterate_to_fixpoint()
 223         .into_results_cursor(&body);
 224
 225     let locals_are_invalidated_at_exit = tcx.hir().body_owner_kind(id).is_fn_or_closure();
 226     let borrow_set =
 227         Rc::new(BorrowSet::build(tcx, body, locals_are_invalidated_at_exit, &mdpe.move_data));
 228
 229     let use_polonius = return_body_with_facts || infcx.tcx.sess.opts.debugging_opts.polonius;
 230
 231     // Compute non-lexical lifetimes.
 232     let nll::NllOutput {
 233         regioncx,
 234         opaque_type_values,
 235         polonius_input,
 236         polonius_output,
 237         opt_closure_req,
 238         nll_errors,
 239     } = nll::compute_regions(
 240         infcx,
 241         free_regions,
 242         body,
 243         &promoted,
 244         location_table,
 245         param_env,
 246         &mut flow_inits,
 247         &mdpe.move_data,
 248         &borrow_set,
 249         &upvars,
 250         use_polonius,
 251     );
 252
 253     // Dump MIR results into a file, if that is enabled. This let us
 254     // write unit-tests, as well as helping with debugging.
 255     nll::dump_mir_results(infcx, &body, &regioncx, &opt_closure_req);
 256
 257     // We also have a `#[rustc_regions]` annotation that causes us to dump
 258     // information.
 259     nll::dump_annotation(
 260         infcx,
 261         &body,
 262         &regioncx,
 263         &opt_closure_req,
 264         &opaque_type_values,
 265         &mut errors_buffer,
 266     );
 267
 268     // The various `flow_*` structures can be large. We drop `flow_inits` here
 269     // so it doesn't overlap with the others below. This reduces peak memory
 270     // usage significantly on some benchmarks.
 271     drop(flow_inits);
 272
 273     let regioncx = Rc::new(regioncx);
 274
 275     let flow_borrows = Borrows::new(tcx, body, &regioncx, &borrow_set)
 276         .into_engine(tcx, body)
 277         .pass_name("borrowck")
 278         .iterate_to_fixpoint();
 279     let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &mdpe)
 280         .into_engine(tcx, body)
 281         .pass_name("borrowck")
 282         .iterate_to_fixpoint();
 283     let flow_ever_inits = EverInitializedPlaces::new(tcx, body, &mdpe)
 284         .into_engine(tcx, body)
 285         .pass_name("borrowck")
 286         .iterate_to_fixpoint();
 287
 288     let movable_generator = !matches!(
 289         tcx.hir().get(id),
 290         Node::Expr(&hir::Expr {
 291             kind: hir::ExprKind::Closure(.., Some(hir::Movability::Static)),
 292             ..
 293         })
 294     );
 295
 296     for (idx, move_data_results) in promoted_errors {
 297         let promoted_body = &promoted[idx];
 298
 299         if let Err((move_data, move_errors)) = move_data_results {
 300             let mut promoted_mbcx = MirBorrowckCtxt {
 301                 infcx,
 302                 param_env,
 303                 body: promoted_body,
 304                 move_data: &move_data,
 305                 location_table, // no need to create a real one for the promoted, it is not used
 306                 movable_generator,
 307                 fn_self_span_reported: Default::default(),
 308                 locals_are_invalidated_at_exit,
 309                 access_place_error_reported: Default::default(),
 310                 reservation_error_reported: Default::default(),
 311                 reservation_warnings: Default::default(),
 312                 move_error_reported: BTreeMap::new(),
 313                 uninitialized_error_reported: Default::default(),
 314                 errors_buffer,
 315                 regioncx: regioncx.clone(),
 316                 used_mut: Default::default(),
 317                 used_mut_upvars: SmallVec::new(),
 318                 borrow_set: Rc::clone(&borrow_set),
 319                 dominators: Dominators::dummy(), // not used
 320                 upvars: Vec::new(),
 321                 local_names: IndexVec::from_elem(None, &promoted_body.local_decls),
 322                 region_names: RefCell::default(),
 323                 next_region_name: RefCell::new(1),
 324                 polonius_output: None,
 325             };
 326             promoted_mbcx.report_move_errors(move_errors);
 327             errors_buffer = promoted_mbcx.errors_buffer;
 328         };
 329     }
 330
 331     let dominators = body.dominators();
 332
 333     let mut mbcx = MirBorrowckCtxt {
 334         infcx,
 335         param_env,
 336         body,
 337         move_data: &mdpe.move_data,
 338         location_table,
 339         movable_generator,
 340         locals_are_invalidated_at_exit,
 341         fn_self_span_reported: Default::default(),
 342         access_place_error_reported: Default::default(),
 343         reservation_error_reported: Default::default(),
 344         reservation_warnings: Default::default(),
 345         move_error_reported: BTreeMap::new(),
 346         uninitialized_error_reported: Default::default(),
 347         errors_buffer,
 348         regioncx: Rc::clone(&regioncx),
 349         used_mut: Default::default(),
 350         used_mut_upvars: SmallVec::new(),
 351         borrow_set: Rc::clone(&borrow_set),
 352         dominators,
 353         upvars,
 354         local_names,
 355         region_names: RefCell::default(),
 356         next_region_name: RefCell::new(1),
 357         polonius_output,
 358     };
 359
 360     // Compute and report region errors, if any.
 361     mbcx.report_region_errors(nll_errors);
 362
 363     let results = BorrowckResults {
 364         ever_inits: flow_ever_inits,
 365         uninits: flow_uninits,
 366         borrows: flow_borrows,
 367     };
 368
 369     mbcx.report_move_errors(move_errors);
 370
 371     rustc_mir_dataflow::visit_results(
 372         body,
 373         traversal::reverse_postorder(body).map(|(bb, _)| bb),
 374         &results,
 375         &mut mbcx,
 376     );
 377
 378     // Convert any reservation warnings into lints.
 379     let reservation_warnings = mem::take(&mut mbcx.reservation_warnings);
 380     for (_, (place, span, location, bk, borrow)) in reservation_warnings {
 381         let mut initial_diag = mbcx.report_conflicting_borrow(location, (place, span), bk, &borrow);
 382
 383         let scope = mbcx.body.source_info(location).scope;
 384         let lint_root = match &mbcx.body.source_scopes[scope].local_data {
 385             ClearCrossCrate::Set(data) => data.lint_root,
 386             _ => id,
 387         };
 388
 389         // Span and message don't matter; we overwrite them below anyway
 390         mbcx.infcx.tcx.struct_span_lint_hir(
 391             MUTABLE_BORROW_RESERVATION_CONFLICT,
 392             lint_root,
 393             DUMMY_SP,
 394             |lint| {
 395                 let mut diag = lint.build("");
 396
 397                 diag.message = initial_diag.styled_message().clone();
 398                 diag.span = initial_diag.span.clone();
 399
 400                 diag.buffer(&mut mbcx.errors_buffer);
 401             },
 402         );
 403         initial_diag.cancel();
 404     }
 405
 406     // For each non-user used mutable variable, check if it's been assigned from
 407     // a user-declared local. If so, then put that local into the used_mut set.
 408     // Note that this set is expected to be small - only upvars from closures
 409     // would have a chance of erroneously adding non-user-defined mutable vars
 410     // to the set.
 411     let temporary_used_locals: FxHashSet<Local> = mbcx
 412         .used_mut
 413         .iter()
 414         .filter(|&local| !mbcx.body.local_decls[*local].is_user_variable())
 415         .cloned()
 416         .collect();
 417     // For the remaining unused locals that are marked as mutable, we avoid linting any that
 418     // were never initialized. These locals may have been removed as unreachable code; or will be
 419     // linted as unused variables.
 420     let unused_mut_locals =
 421         mbcx.body.mut_vars_iter().filter(|local| !mbcx.used_mut.contains(local)).collect();
 422     mbcx.gather_used_muts(temporary_used_locals, unused_mut_locals);
 423
 424     debug!("mbcx.used_mut: {:?}", mbcx.used_mut);
 425     let used_mut = mbcx.used_mut;
 426     for local in mbcx.body.mut_vars_and_args_iter().filter(|local| !used_mut.contains(local)) {
 427         let local_decl = &mbcx.body.local_decls[local];
 428         let lint_root = match &mbcx.body.source_scopes[local_decl.source_info.scope].local_data {
 429             ClearCrossCrate::Set(data) => data.lint_root,
 430             _ => continue,
 431         };
 432
 433         // Skip over locals that begin with an underscore or have no name
 434         match mbcx.local_names[local] {
 435             Some(name) => {
 436                 if name.as_str().starts_with('_') {
 437                     continue;
 438                 }
 439             }
 440             None => continue,
 441         }
 442
 443         let span = local_decl.source_info.span;
 444         if span.desugaring_kind().is_some() {
 445             // If the `mut` arises as part of a desugaring, we should ignore it.
 446             continue;
 447         }
 448
 449         tcx.struct_span_lint_hir(UNUSED_MUT, lint_root, span, |lint| {
 450             let mut_span = tcx.sess.source_map().span_until_non_whitespace(span);
 451             lint.build("variable does not need to be mutable")
 452                 .span_suggestion_short(
 453                     mut_span,
 454                     "remove this `mut`",
 455                     String::new(),
 456                     Applicability::MachineApplicable,
 457                 )
 458                 .emit();
 459         })
 460     }
 461
 462     // Buffer any move errors that we collected and de-duplicated.
 463     for (_, (_, diag)) in mbcx.move_error_reported {
 464         diag.buffer(&mut mbcx.errors_buffer);
 465     }
 466
 467     if !mbcx.errors_buffer.is_empty() {
 468         mbcx.errors_buffer.sort_by_key(|diag| diag.sort_span);
 469
 470         for diag in mbcx.errors_buffer.drain(..) {
 471             mbcx.infcx.tcx.sess.diagnostic().emit_diagnostic(&diag);
 472         }
 473     }
 474
 475     let result = BorrowCheckResult {
 476         concrete_opaque_types: opaque_type_values,
 477         closure_requirements: opt_closure_req,
 478         used_mut_upvars: mbcx.used_mut_upvars,
 479     };
 480
 481     let body_with_facts = if return_body_with_facts {
 482         let output_facts = mbcx.polonius_output.expect("Polonius output was not computed");
 483         Some(Box::new(BodyWithBorrowckFacts {
 484             body: body_owned,
 485             input_facts: *polonius_input.expect("Polonius input facts were not generated"),
 486             output_facts,
 487             location_table: location_table_owned,
 488         }))
 489     } else {
 490         None
 491     };
 492
 493     debug!("do_mir_borrowck: result = {:#?}", result);
 494
 495     (result, body_with_facts)
 496 }
 497
 498 /// A `Body` with information computed by the borrow checker. This struct is
 499 /// intended to be consumed by compiler consumers.
 500 ///
 501 /// We need to include the MIR body here because the region identifiers must
 502 /// match the ones in the Polonius facts.
 503 pub struct BodyWithBorrowckFacts<'tcx> {
 504     /// A mir body that contains region identifiers.
 505     pub body: Body<'tcx>,
 506     /// Polonius input facts.
 507     pub input_facts: AllFacts,
 508     /// Polonius output facts.
 509     pub output_facts: Rc<self::nll::PoloniusOutput>,
 510     /// The table that maps Polonius points to locations in the table.
 511     pub location_table: LocationTable,
 512 }
 513
 514 struct MirBorrowckCtxt<'cx, 'tcx> {
 515     infcx: &'cx InferCtxt<'cx, 'tcx>,
 516     param_env: ParamEnv<'tcx>,
 517     body: &'cx Body<'tcx>,
 518     move_data: &'cx MoveData<'tcx>,
 519
 520     /// Map from MIR `Location` to `LocationIndex`; created
 521     /// when MIR borrowck begins.
 522     location_table: &'cx LocationTable,
 523
 524     movable_generator: bool,
 525     /// This keeps track of whether local variables are free-ed when the function
 526     /// exits even without a `StorageDead`, which appears to be the case for
 527     /// constants.
 528     ///
 529     /// I'm not sure this is the right approach - @eddyb could you try and
 530     /// figure this out?
 531     locals_are_invalidated_at_exit: bool,
 532     /// This field keeps track of when borrow errors are reported in the access_place function
 533     /// so that there is no duplicate reporting. This field cannot also be used for the conflicting
 534     /// borrow errors that is handled by the `reservation_error_reported` field as the inclusion
 535     /// of the `Span` type (while required to mute some errors) stops the muting of the reservation
 536     /// errors.
 537     access_place_error_reported: FxHashSet<(Place<'tcx>, Span)>,
 538     /// This field keeps track of when borrow conflict errors are reported
 539     /// for reservations, so that we don't report seemingly duplicate
 540     /// errors for corresponding activations.
 541     //
 542     // FIXME: ideally this would be a set of `BorrowIndex`, not `Place`s,
 543     // but it is currently inconvenient to track down the `BorrowIndex`
 544     // at the time we detect and report a reservation error.
 545     reservation_error_reported: FxHashSet<Place<'tcx>>,
 546     /// This fields keeps track of the `Span`s that we have
 547     /// used to report extra information for `FnSelfUse`, to avoid
 548     /// unnecessarily verbose errors.
 549     fn_self_span_reported: FxHashSet<Span>,
 550     /// Migration warnings to be reported for #56254. We delay reporting these
 551     /// so that we can suppress the warning if there's a corresponding error
 552     /// for the activation of the borrow.
 553     reservation_warnings:
 554         FxHashMap<BorrowIndex, (Place<'tcx>, Span, Location, BorrowKind, BorrowData<'tcx>)>,
 555     /// This field keeps track of move errors that are to be reported for given move indices.
 556     ///
 557     /// There are situations where many errors can be reported for a single move out (see #53807)
 558     /// and we want only the best of those errors.
 559     ///
 560     /// The `report_use_of_moved_or_uninitialized` function checks this map and replaces the
 561     /// diagnostic (if there is one) if the `Place` of the error being reported is a prefix of the
 562     /// `Place` of the previous most diagnostic. This happens instead of buffering the error. Once
 563     /// all move errors have been reported, any diagnostics in this map are added to the buffer
 564     /// to be emitted.
 565     ///
 566     /// `BTreeMap` is used to preserve the order of insertions when iterating. This is necessary
 567     /// when errors in the map are being re-added to the error buffer so that errors with the
 568     /// same primary span come out in a consistent order.
 569     move_error_reported: BTreeMap<Vec<MoveOutIndex>, (PlaceRef<'tcx>, DiagnosticBuilder<'cx>)>,
 570     /// This field keeps track of errors reported in the checking of uninitialized variables,
 571     /// so that we don't report seemingly duplicate errors.
 572     uninitialized_error_reported: FxHashSet<PlaceRef<'tcx>>,
 573     /// Errors to be reported buffer
 574     errors_buffer: Vec<Diagnostic>,
 575     /// This field keeps track of all the local variables that are declared mut and are mutated.
 576     /// Used for the warning issued by an unused mutable local variable.
 577     used_mut: FxHashSet<Local>,
 578     /// If the function we're checking is a closure, then we'll need to report back the list of
 579     /// mutable upvars that have been used. This field keeps track of them.
 580     used_mut_upvars: SmallVec<[Field; 8]>,
 581     /// Region inference context. This contains the results from region inference and lets us e.g.
 582     /// find out which CFG points are contained in each borrow region.
 583     regioncx: Rc<RegionInferenceContext<'tcx>>,
 584
 585     /// The set of borrows extracted from the MIR
 586     borrow_set: Rc<BorrowSet<'tcx>>,
 587
 588     /// Dominators for MIR
 589     dominators: Dominators<BasicBlock>,
 590
 591     /// Information about upvars not necessarily preserved in types or MIR
 592     upvars: Vec<Upvar<'tcx>>,
 593
 594     /// Names of local (user) variables (extracted from `var_debug_info`).
 595     local_names: IndexVec<Local, Option<Symbol>>,
 596
 597     /// Record the region names generated for each region in the given
 598     /// MIR def so that we can reuse them later in help/error messages.
 599     region_names: RefCell<FxHashMap<RegionVid, RegionName>>,
 600
 601     /// The counter for generating new region names.
 602     next_region_name: RefCell<usize>,
 603
 604     /// Results of Polonius analysis.
 605     polonius_output: Option<Rc<PoloniusOutput>>,
 606 }
 607
 608 // Check that:
 609 // 1. assignments are always made to mutable locations (FIXME: does that still really go here?)
 610 // 2. loans made in overlapping scopes do not conflict
 611 // 3. assignments do not affect things loaned out as immutable
 612 // 4. moves do not affect things loaned out in any way
 613 impl<'cx, 'tcx> rustc_mir_dataflow::ResultsVisitor<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx> {
 614     type FlowState = Flows<'cx, 'tcx>;
 615
 616     fn visit_statement_before_primary_effect(
 617         &mut self,
 618         flow_state: &Flows<'cx, 'tcx>,
 619         stmt: &'cx Statement<'tcx>,
 620         location: Location,
 621     ) {
 622         debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {:?}", location, stmt, flow_state);
 623         let span = stmt.source_info.span;
 624
 625         self.check_activations(location, span, flow_state);
 626
 627         match &stmt.kind {
 628             StatementKind::Assign(box (lhs, ref rhs)) => {
 629                 self.consume_rvalue(location, (rhs, span), flow_state);
 630
 631                 self.mutate_place(location, (*lhs, span), Shallow(None), flow_state);
 632             }
 633             StatementKind::FakeRead(box (_, ref place)) => {
 634                 // Read for match doesn't access any memory and is used to
 635                 // assert that a place is safe and live. So we don't have to
 636                 // do any checks here.
 637                 //
 638                 // FIXME: Remove check that the place is initialized. This is
 639                 // needed for now because matches don't have never patterns yet.
 640                 // So this is the only place we prevent
 641                 //      let x: !;
 642                 //      match x {};
 643                 // from compiling.
 644                 self.check_if_path_or_subpath_is_moved(
 645                     location,
 646                     InitializationRequiringAction::Use,
 647                     (place.as_ref(), span),
 648                     flow_state,
 649                 );
 650             }
 651             StatementKind::SetDiscriminant { place, variant_index: _ } => {
 652                 self.mutate_place(location, (**place, span), Shallow(None), flow_state);
 653             }
 654             StatementKind::CopyNonOverlapping(box rustc_middle::mir::CopyNonOverlapping {
 655                 ..
 656             }) => {
 657                 span_bug!(
 658                     span,
 659                     "Unexpected CopyNonOverlapping, should only appear after lower_intrinsics",
 660                 )
 661             }
 662             StatementKind::Nop
 663             | StatementKind::Coverage(..)
 664             | StatementKind::AscribeUserType(..)
 665             | StatementKind::Retag { .. }
 666             | StatementKind::StorageLive(..) => {
 667                 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
 668                 // to borrow check.
 669             }
 670             StatementKind::StorageDead(local) => {
 671                 self.access_place(
 672                     location,
 673                     (Place::from(*local), span),
 674                     (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
 675                     LocalMutationIsAllowed::Yes,
 676                     flow_state,
 677                 );
 678             }
 679         }
 680     }
 681
 682     fn visit_terminator_before_primary_effect(
 683         &mut self,
 684         flow_state: &Flows<'cx, 'tcx>,
 685         term: &'cx Terminator<'tcx>,
 686         loc: Location,
 687     ) {
 688         debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {:?}", loc, term, flow_state);
 689         let span = term.source_info.span;
 690
 691         self.check_activations(loc, span, flow_state);
 692
 693         match term.kind {
 694             TerminatorKind::SwitchInt { ref discr, switch_ty: _, targets: _ } => {
 695                 self.consume_operand(loc, (discr, span), flow_state);
 696             }
 697             TerminatorKind::Drop { place, target: _, unwind: _ } => {
 698                 debug!(
 699                     "visit_terminator_drop \
 700                      loc: {:?} term: {:?} place: {:?} span: {:?}",
 701                     loc, term, place, span
 702                 );
 703
 704                 self.access_place(
 705                     loc,
 706                     (place, span),
 707                     (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
 708                     LocalMutationIsAllowed::Yes,
 709                     flow_state,
 710                 );
 711             }
 712             TerminatorKind::DropAndReplace {
 713                 place: drop_place,
 714                 value: ref new_value,
 715                 target: _,
 716                 unwind: _,
 717             } => {
 718                 self.mutate_place(loc, (drop_place, span), Deep, flow_state);
 719                 self.consume_operand(loc, (new_value, span), flow_state);
 720             }
 721             TerminatorKind::Call {
 722                 ref func,
 723                 ref args,
 724                 ref destination,
 725                 cleanup: _,
 726                 from_hir_call: _,
 727                 fn_span: _,
 728             } => {
 729                 self.consume_operand(loc, (func, span), flow_state);
 730                 for arg in args {
 731                     self.consume_operand(loc, (arg, span), flow_state);
 732                 }
 733                 if let Some((dest, _ /*bb*/)) = *destination {
 734                     self.mutate_place(loc, (dest, span), Deep, flow_state);
 735                 }
 736             }
 737             TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
 738                 self.consume_operand(loc, (cond, span), flow_state);
 739                 use rustc_middle::mir::AssertKind;
 740                 if let AssertKind::BoundsCheck { ref len, ref index } = *msg {
 741                     self.consume_operand(loc, (len, span), flow_state);
 742                     self.consume_operand(loc, (index, span), flow_state);
 743                 }
 744             }
 745
 746             TerminatorKind::Yield { ref value, resume: _, resume_arg, drop: _ } => {
 747                 self.consume_operand(loc, (value, span), flow_state);
 748                 self.mutate_place(loc, (resume_arg, span), Deep, flow_state);
 749             }
 750
 751             TerminatorKind::InlineAsm {
 752                 template: _,
 753                 ref operands,
 754                 options: _,
 755                 line_spans: _,
 756                 destination: _,
 757                 cleanup: _,
 758             } => {
 759                 for op in operands {
 760                     match *op {
 761                         InlineAsmOperand::In { reg: _, ref value } => {
 762                             self.consume_operand(loc, (value, span), flow_state);
 763                         }
 764                         InlineAsmOperand::Out { reg: _, late: _, place, .. } => {
 765                             if let Some(place) = place {
 766                                 self.mutate_place(loc, (place, span), Shallow(None), flow_state);
 767                             }
 768                         }
 769                         InlineAsmOperand::InOut { reg: _, late: _, ref in_value, out_place } => {
 770                             self.consume_operand(loc, (in_value, span), flow_state);
 771                             if let Some(out_place) = out_place {
 772                                 self.mutate_place(
 773                                     loc,
 774                                     (out_place, span),
 775                                     Shallow(None),
 776                                     flow_state,
 777                                 );
 778                             }
 779                         }
 780                         InlineAsmOperand::Const { value: _ }
 781                         | InlineAsmOperand::SymFn { value: _ }
 782                         | InlineAsmOperand::SymStatic { def_id: _ } => {}
 783                     }
 784                 }
 785             }
 786
 787             TerminatorKind::Goto { target: _ }
 788             | TerminatorKind::Abort
 789             | TerminatorKind::Unreachable
 790             | TerminatorKind::Resume
 791             | TerminatorKind::Return
 792             | TerminatorKind::GeneratorDrop
 793             | TerminatorKind::FalseEdge { real_target: _, imaginary_target: _ }
 794             | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
 795                 // no data used, thus irrelevant to borrowck
 796             }
 797         }
 798     }
 799
 800     fn visit_terminator_after_primary_effect(
 801         &mut self,
 802         flow_state: &Flows<'cx, 'tcx>,
 803         term: &'cx Terminator<'tcx>,
 804         loc: Location,
 805     ) {
 806         let span = term.source_info.span;
 807
 808         match term.kind {
 809             TerminatorKind::Yield { value: _, resume: _, resume_arg: _, drop: _ } => {
 810                 if self.movable_generator {
 811                     // Look for any active borrows to locals
 812                     let borrow_set = self.borrow_set.clone();
 813                     for i in flow_state.borrows.iter() {
 814                         let borrow = &borrow_set[i];
 815                         self.check_for_local_borrow(borrow, span);
 816                     }
 817                 }
 818             }
 819
 820             TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
 821                 // Returning from the function implicitly kills storage for all locals and statics.
 822                 // Often, the storage will already have been killed by an explicit
 823                 // StorageDead, but we don't always emit those (notably on unwind paths),
 824                 // so this "extra check" serves as a kind of backup.
 825                 let borrow_set = self.borrow_set.clone();
 826                 for i in flow_state.borrows.iter() {
 827                     let borrow = &borrow_set[i];
 828                     self.check_for_invalidation_at_exit(loc, borrow, span);
 829                 }
 830             }
 831
 832             TerminatorKind::Abort
 833             | TerminatorKind::Assert { .. }
 834             | TerminatorKind::Call { .. }
 835             | TerminatorKind::Drop { .. }
 836             | TerminatorKind::DropAndReplace { .. }
 837             | TerminatorKind::FalseEdge { real_target: _, imaginary_target: _ }
 838             | TerminatorKind::FalseUnwind { real_target: _, unwind: _ }
 839             | TerminatorKind::Goto { .. }
 840             | TerminatorKind::SwitchInt { .. }
 841             | TerminatorKind::Unreachable
 842             | TerminatorKind::InlineAsm { .. } => {}
 843         }
 844     }
 845 }
 846
 847 use self::AccessDepth::{Deep, Shallow};
 848 use self::ReadOrWrite::{Activation, Read, Reservation, Write};
 849
 850 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 851 enum ArtificialField {
 852     ArrayLength,
 853     ShallowBorrow,
 854 }
 855
 856 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 857 enum AccessDepth {
 858     /// From the RFC: "A *shallow* access means that the immediate
 859     /// fields reached at P are accessed, but references or pointers
 860     /// found within are not dereferenced. Right now, the only access
 861     /// that is shallow is an assignment like `x = ...;`, which would
 862     /// be a *shallow write* of `x`."
 863     Shallow(Option<ArtificialField>),
 864
 865     /// From the RFC: "A *deep* access means that all data reachable
 866     /// through the given place may be invalidated or accesses by
 867     /// this action."
 868     Deep,
 869
 870     /// Access is Deep only when there is a Drop implementation that
 871     /// can reach the data behind the reference.
 872     Drop,
 873 }
 874
 875 /// Kind of access to a value: read or write
 876 /// (For informational purposes only)
 877 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 878 enum ReadOrWrite {
 879     /// From the RFC: "A *read* means that the existing data may be
 880     /// read, but will not be changed."
 881     Read(ReadKind),
 882
 883     /// From the RFC: "A *write* means that the data may be mutated to
 884     /// new values or otherwise invalidated (for example, it could be
 885     /// de-initialized, as in a move operation).
 886     Write(WriteKind),
 887
 888     /// For two-phase borrows, we distinguish a reservation (which is treated
 889     /// like a Read) from an activation (which is treated like a write), and
 890     /// each of those is furthermore distinguished from Reads/Writes above.
 891     Reservation(WriteKind),
 892     Activation(WriteKind, BorrowIndex),
 893 }
 894
 895 /// Kind of read access to a value
 896 /// (For informational purposes only)
 897 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 898 enum ReadKind {
 899     Borrow(BorrowKind),
 900     Copy,
 901 }
 902
 903 /// Kind of write access to a value
 904 /// (For informational purposes only)
 905 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 906 enum WriteKind {
 907     StorageDeadOrDrop,
 908     MutableBorrow(BorrowKind),
 909     Mutate,
 910     Move,
 911 }
 912
 913 /// When checking permissions for a place access, this flag is used to indicate that an immutable
 914 /// local place can be mutated.
 915 //
 916 // FIXME: @nikomatsakis suggested that this flag could be removed with the following modifications:
 917 // - Merge `check_access_permissions()` and `check_if_reassignment_to_immutable_state()`.
 918 // - Split `is_mutable()` into `is_assignable()` (can be directly assigned) and
 919 //   `is_declared_mutable()`.
 920 // - Take flow state into consideration in `is_assignable()` for local variables.
 921 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 922 enum LocalMutationIsAllowed {
 923     Yes,
 924     /// We want use of immutable upvars to cause a "write to immutable upvar"
 925     /// error, not an "reassignment" error.
 926     ExceptUpvars,
 927     No,
 928 }
 929
 930 #[derive(Copy, Clone, Debug)]
 931 enum InitializationRequiringAction {
 932     Borrow,
 933     MatchOn,
 934     Use,
 935     Assignment,
 936     PartialAssignment,
 937 }
 938
 939 struct RootPlace<'tcx> {
 940     place_local: Local,
 941     place_projection: &'tcx [PlaceElem<'tcx>],
 942     is_local_mutation_allowed: LocalMutationIsAllowed,
 943 }
 944
 945 impl InitializationRequiringAction {
 946     fn as_noun(self) -> &'static str {
 947         match self {
 948             InitializationRequiringAction::Borrow => "borrow",
 949             InitializationRequiringAction::MatchOn => "use", // no good noun
 950             InitializationRequiringAction::Use => "use",
 951             InitializationRequiringAction::Assignment => "assign",
 952             InitializationRequiringAction::PartialAssignment => "assign to part",
 953         }
 954     }
 955
 956     fn as_verb_in_past_tense(self) -> &'static str {
 957         match self {
 958             InitializationRequiringAction::Borrow => "borrowed",
 959             InitializationRequiringAction::MatchOn => "matched on",
 960             InitializationRequiringAction::Use => "used",
 961             InitializationRequiringAction::Assignment => "assigned",
 962             InitializationRequiringAction::PartialAssignment => "partially assigned",
 963         }
 964     }
 965 }
 966
 967 impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
 968     fn body(&self) -> &'cx Body<'tcx> {
 969         self.body
 970     }
 971
 972     /// Checks an access to the given place to see if it is allowed. Examines the set of borrows
 973     /// that are in scope, as well as which paths have been initialized, to ensure that (a) the
 974     /// place is initialized and (b) it is not borrowed in some way that would prevent this
 975     /// access.
 976     ///
 977     /// Returns `true` if an error is reported.
 978     fn access_place(
 979         &mut self,
 980         location: Location,
 981         place_span: (Place<'tcx>, Span),
 982         kind: (AccessDepth, ReadOrWrite),
 983         is_local_mutation_allowed: LocalMutationIsAllowed,
 984         flow_state: &Flows<'cx, 'tcx>,
 985     ) {
 986         let (sd, rw) = kind;
 987
 988         if let Activation(_, borrow_index) = rw {
 989             if self.reservation_error_reported.contains(&place_span.0) {
 990                 debug!(
 991                     "skipping access_place for activation of invalid reservation \
 992                      place: {:?} borrow_index: {:?}",
 993                     place_span.0, borrow_index
 994                 );
 995                 return;
 996             }
 997         }
 998
 999         // Check is_empty() first because it's the common case, and doing that
1000         // way we avoid the clone() call.
1001         if !self.access_place_error_reported.is_empty()
1002             && self.access_place_error_reported.contains(&(place_span.0, place_span.1))
1003         {
1004             debug!(
1005                 "access_place: suppressing error place_span=`{:?}` kind=`{:?}`",
1006                 place_span, kind
1007             );
1008             return;
1009         }
1010
1011         let mutability_error = self.check_access_permissions(
1012             place_span,
1013             rw,
1014             is_local_mutation_allowed,
1015             flow_state,
1016             location,
1017         );
1018         let conflict_error =
1019             self.check_access_for_conflict(location, place_span, sd, rw, flow_state);
1020
1021         if let (Activation(_, borrow_idx), true) = (kind.1, conflict_error) {
1022             // Suppress this warning when there's an error being emitted for the
1023             // same borrow: fixing the error is likely to fix the warning.
1024             self.reservation_warnings.remove(&borrow_idx);
1025         }
1026
1027         if conflict_error || mutability_error {
1028             debug!("access_place: logging error place_span=`{:?}` kind=`{:?}`", place_span, kind);
1029
1030             self.access_place_error_reported.insert((place_span.0, place_span.1));
1031         }
1032     }
1033
1034     fn check_access_for_conflict(
1035         &mut self,
1036         location: Location,
1037         place_span: (Place<'tcx>, Span),
1038         sd: AccessDepth,
1039         rw: ReadOrWrite,
1040         flow_state: &Flows<'cx, 'tcx>,
1041     ) -> bool {
1042         debug!(
1043             "check_access_for_conflict(location={:?}, place_span={:?}, sd={:?}, rw={:?})",
1044             location, place_span, sd, rw,
1045         );
1046
1047         let mut error_reported = false;
1048         let tcx = self.infcx.tcx;
1049         let body = self.body;
1050         let borrow_set = self.borrow_set.clone();
1051
1052         // Use polonius output if it has been enabled.
1053         let polonius_output = self.polonius_output.clone();
1054         let borrows_in_scope = if let Some(polonius) = &polonius_output {
1055             let location = self.location_table.start_index(location);
1056             Either::Left(polonius.errors_at(location).iter().copied())
1057         } else {
1058             Either::Right(flow_state.borrows.iter())
1059         };
1060
1061         each_borrow_involving_path(
1062             self,
1063             tcx,
1064             body,
1065             location,
1066             (sd, place_span.0),
1067             &borrow_set,
1068             borrows_in_scope,
1069             |this, borrow_index, borrow| match (rw, borrow.kind) {
1070                 // Obviously an activation is compatible with its own
1071                 // reservation (or even prior activating uses of same
1072                 // borrow); so don't check if they interfere.
1073                 //
1074                 // NOTE: *reservations* do conflict with themselves;
1075                 // thus aren't injecting unsoundenss w/ this check.)
1076                 (Activation(_, activating), _) if activating == borrow_index => {
1077                     debug!(
1078                         "check_access_for_conflict place_span: {:?} sd: {:?} rw: {:?} \
1079                          skipping {:?} b/c activation of same borrow_index",
1080                         place_span,
1081                         sd,
1082                         rw,
1083                         (borrow_index, borrow),
1084                     );
1085                     Control::Continue
1086                 }
1087
1088                 (Read(_), BorrowKind::Shared | BorrowKind::Shallow)
1089                 | (
1090                     Read(ReadKind::Borrow(BorrowKind::Shallow)),
1091                     BorrowKind::Unique | BorrowKind::Mut { .. },
1092                 ) => Control::Continue,
1093
1094                 (Write(WriteKind::Move), BorrowKind::Shallow) => {
1095                     // Handled by initialization checks.
1096                     Control::Continue
1097                 }
1098
1099                 (Read(kind), BorrowKind::Unique | BorrowKind::Mut { .. }) => {
1100                     // Reading from mere reservations of mutable-borrows is OK.
1101                     if !is_active(&this.dominators, borrow, location) {
1102                         assert!(allow_two_phase_borrow(borrow.kind));
1103                         return Control::Continue;
1104                     }
1105
1106                     error_reported = true;
1107                     match kind {
1108                         ReadKind::Copy => {
1109                             this.report_use_while_mutably_borrowed(location, place_span, borrow)
1110                                 .buffer(&mut this.errors_buffer);
1111                         }
1112                         ReadKind::Borrow(bk) => {
1113                             this.report_conflicting_borrow(location, place_span, bk, borrow)
1114                                 .buffer(&mut this.errors_buffer);
1115                         }
1116                     }
1117                     Control::Break
1118                 }
1119
1120                 (
1121                     Reservation(WriteKind::MutableBorrow(bk)),
1122                     BorrowKind::Shallow | BorrowKind::Shared,
1123                 ) if { tcx.migrate_borrowck() && this.borrow_set.contains(&location) } => {
1124                     let bi = this.borrow_set.get_index_of(&location).unwrap();
1125                     debug!(
1126                         "recording invalid reservation of place: {:?} with \
1127                          borrow index {:?} as warning",
1128                         place_span.0, bi,
1129                     );
1130                     // rust-lang/rust#56254 - This was previously permitted on
1131                     // the 2018 edition so we emit it as a warning. We buffer
1132                     // these sepately so that we only emit a warning if borrow
1133                     // checking was otherwise successful.
1134                     this.reservation_warnings
1135                         .insert(bi, (place_span.0, place_span.1, location, bk, borrow.clone()));
1136
1137                     // Don't suppress actual errors.
1138                     Control::Continue
1139                 }
1140
1141                 (Reservation(kind) | Activation(kind, _) | Write(kind), _) => {
1142                     match rw {
1143                         Reservation(..) => {
1144                             debug!(
1145                                 "recording invalid reservation of \
1146                                  place: {:?}",
1147                                 place_span.0
1148                             );
1149                             this.reservation_error_reported.insert(place_span.0);
1150                         }
1151                         Activation(_, activating) => {
1152                             debug!(
1153                                 "observing check_place for activation of \
1154                                  borrow_index: {:?}",
1155                                 activating
1156                             );
1157                         }
1158                         Read(..) | Write(..) => {}
1159                     }
1160
1161                     error_reported = true;
1162                     match kind {
1163                         WriteKind::MutableBorrow(bk) => {
1164                             this.report_conflicting_borrow(location, place_span, bk, borrow)
1165                                 .buffer(&mut this.errors_buffer);
1166                         }
1167                         WriteKind::StorageDeadOrDrop => this
1168                             .report_borrowed_value_does_not_live_long_enough(
1169                                 location,
1170                                 borrow,
1171                                 place_span,
1172                                 Some(kind),
1173                             ),
1174                         WriteKind::Mutate => {
1175                             this.report_illegal_mutation_of_borrowed(location, place_span, borrow)
1176                         }
1177                         WriteKind::Move => {
1178                             this.report_move_out_while_borrowed(location, place_span, borrow)
1179                         }
1180                     }
1181                     Control::Break
1182                 }
1183             },
1184         );
1185
1186         error_reported
1187     }
1188
1189     fn mutate_place(
1190         &mut self,
1191         location: Location,
1192         place_span: (Place<'tcx>, Span),
1193         kind: AccessDepth,
1194         flow_state: &Flows<'cx, 'tcx>,
1195     ) {
1196         // Write of P[i] or *P requires P init'd.
1197         self.check_if_assigned_path_is_moved(location, place_span, flow_state);
1198
1199         // Special case: you can assign an immutable local variable
1200         // (e.g., `x = ...`) so long as it has never been initialized
1201         // before (at this point in the flow).
1202         if let Some(local) = place_span.0.as_local() {
1203             if let Mutability::Not = self.body.local_decls[local].mutability {
1204                 // check for reassignments to immutable local variables
1205                 self.check_if_reassignment_to_immutable_state(
1206                     location, local, place_span, flow_state,
1207                 );
1208                 return;
1209             }
1210         }
1211
1212         // Otherwise, use the normal access permission rules.
1213         self.access_place(
1214             location,
1215             place_span,
1216             (kind, Write(WriteKind::Mutate)),
1217             LocalMutationIsAllowed::No,
1218             flow_state,
1219         );
1220     }
1221
1222     fn consume_rvalue(
1223         &mut self,
1224         location: Location,
1225         (rvalue, span): (&'cx Rvalue<'tcx>, Span),
1226         flow_state: &Flows<'cx, 'tcx>,
1227     ) {
1228         match *rvalue {
1229             Rvalue::Ref(_ /*rgn*/, bk, place) => {
1230                 let access_kind = match bk {
1231                     BorrowKind::Shallow => {
1232                         (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
1233                     }
1234                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
1235                     BorrowKind::Unique | BorrowKind::Mut { .. } => {
1236                         let wk = WriteKind::MutableBorrow(bk);
1237                         if allow_two_phase_borrow(bk) {
1238                             (Deep, Reservation(wk))
1239                         } else {
1240                             (Deep, Write(wk))
1241                         }
1242                     }
1243                 };
1244
1245                 self.access_place(
1246                     location,
1247                     (place, span),
1248                     access_kind,
1249                     LocalMutationIsAllowed::No,
1250                     flow_state,
1251                 );
1252
1253                 let action = if bk == BorrowKind::Shallow {
1254                     InitializationRequiringAction::MatchOn
1255                 } else {
1256                     InitializationRequiringAction::Borrow
1257                 };
1258
1259                 self.check_if_path_or_subpath_is_moved(
1260                     location,
1261                     action,
1262                     (place.as_ref(), span),
1263                     flow_state,
1264                 );
1265             }
1266
1267             Rvalue::AddressOf(mutability, place) => {
1268                 let access_kind = match mutability {
1269                     Mutability::Mut => (
1270                         Deep,
1271                         Write(WriteKind::MutableBorrow(BorrowKind::Mut {
1272                             allow_two_phase_borrow: false,
1273                         })),
1274                     ),
1275                     Mutability::Not => (Deep, Read(ReadKind::Borrow(BorrowKind::Shared))),
1276                 };
1277
1278                 self.access_place(
1279                     location,
1280                     (place, span),
1281                     access_kind,
1282                     LocalMutationIsAllowed::No,
1283                     flow_state,
1284                 );
1285
1286                 self.check_if_path_or_subpath_is_moved(
1287                     location,
1288                     InitializationRequiringAction::Borrow,
1289                     (place.as_ref(), span),
1290                     flow_state,
1291                 );
1292             }
1293
1294             Rvalue::ThreadLocalRef(_) => {}
1295
1296             Rvalue::Use(ref operand)
1297             | Rvalue::Repeat(ref operand, _)
1298             | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
1299             | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/)
1300             | Rvalue::ShallowInitBox(ref operand, _ /*ty*/) => {
1301                 self.consume_operand(location, (operand, span), flow_state)
1302             }
1303
1304             Rvalue::Len(place) | Rvalue::Discriminant(place) => {
1305                 let af = match *rvalue {
1306                     Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
1307                     Rvalue::Discriminant(..) => None,
1308                     _ => unreachable!(),
1309                 };
1310                 self.access_place(
1311                     location,
1312                     (place, span),
1313                     (Shallow(af), Read(ReadKind::Copy)),
1314                     LocalMutationIsAllowed::No,
1315                     flow_state,
1316                 );
1317                 self.check_if_path_or_subpath_is_moved(
1318                     location,
1319                     InitializationRequiringAction::Use,
1320                     (place.as_ref(), span),
1321                     flow_state,
1322                 );
1323             }
1324
1325             Rvalue::BinaryOp(_bin_op, box (ref operand1, ref operand2))
1326             | Rvalue::CheckedBinaryOp(_bin_op, box (ref operand1, ref operand2)) => {
1327                 self.consume_operand(location, (operand1, span), flow_state);
1328                 self.consume_operand(location, (operand2, span), flow_state);
1329             }
1330
1331             Rvalue::NullaryOp(_op, _ty) => {
1332                 // nullary ops take no dynamic input; no borrowck effect.
1333             }
1334
1335             Rvalue::Aggregate(ref aggregate_kind, ref operands) => {
1336                 // We need to report back the list of mutable upvars that were
1337                 // moved into the closure and subsequently used by the closure,
1338                 // in order to populate our used_mut set.
1339                 match **aggregate_kind {
1340                     AggregateKind::Closure(def_id, _) | AggregateKind::Generator(def_id, _, _) => {
1341                         let BorrowCheckResult { used_mut_upvars, .. } =
1342                             self.infcx.tcx.mir_borrowck(def_id.expect_local());
1343                         debug!("{:?} used_mut_upvars={:?}", def_id, used_mut_upvars);
1344                         for field in used_mut_upvars {
1345                             self.propagate_closure_used_mut_upvar(&operands[field.index()]);
1346                         }
1347                     }
1348                     AggregateKind::Adt(..)
1349                     | AggregateKind::Array(..)
1350                     | AggregateKind::Tuple { .. } => (),
1351                 }
1352
1353                 for operand in operands {
1354                     self.consume_operand(location, (operand, span), flow_state);
1355                 }
1356             }
1357         }
1358     }
1359
1360     fn propagate_closure_used_mut_upvar(&mut self, operand: &Operand<'tcx>) {
1361         let propagate_closure_used_mut_place = |this: &mut Self, place: Place<'tcx>| {
1362             // We have three possibilities here:
1363             // a. We are modifying something through a mut-ref
1364             // b. We are modifying something that is local to our parent
1365             // c. Current body is a nested closure, and we are modifying path starting from
1366             //    a Place captured by our parent closure.
1367
1368             // Handle (c), the path being modified is exactly the path captured by our parent
1369             if let Some(field) = this.is_upvar_field_projection(place.as_ref()) {
1370                 this.used_mut_upvars.push(field);
1371                 return;
1372             }
1373
1374             for (place_ref, proj) in place.iter_projections().rev() {
1375                 // Handle (a)
1376                 if proj == ProjectionElem::Deref {
1377                     match place_ref.ty(this.body(), this.infcx.tcx).ty.kind() {
1378                         // We aren't modifying a variable directly
1379                         ty::Ref(_, _, hir::Mutability::Mut) => return,
1380
1381                         _ => {}
1382                     }
1383                 }
1384
1385                 // Handle (c)
1386                 if let Some(field) = this.is_upvar_field_projection(place_ref) {
1387                     this.used_mut_upvars.push(field);
1388                     return;
1389                 }
1390             }
1391
1392             // Handle(b)
1393             this.used_mut.insert(place.local);
1394         };
1395
1396         // This relies on the current way that by-value
1397         // captures of a closure are copied/moved directly
1398         // when generating MIR.
1399         match *operand {
1400             Operand::Move(place) | Operand::Copy(place) => {
1401                 match place.as_local() {
1402                     Some(local) if !self.body.local_decls[local].is_user_variable() => {
1403                         if self.body.local_decls[local].ty.is_mutable_ptr() {
1404                             // The variable will be marked as mutable by the borrow.
1405                             return;
1406                         }
1407                         // This is an edge case where we have a `move` closure
1408                         // inside a non-move closure, and the inner closure
1409                         // contains a mutation:
1410                         //
1411                         // let mut i = 0;
1412                         // || { move || { i += 1; }; };
1413                         //
1414                         // In this case our usual strategy of assuming that the
1415                         // variable will be captured by mutable reference is
1416                         // wrong, since `i` can be copied into the inner
1417                         // closure from a shared reference.
1418                         //
1419                         // As such we have to search for the local that this
1420                         // capture comes from and mark it as being used as mut.
1421
1422                         let temp_mpi = self.move_data.rev_lookup.find_local(local);
1423                         let init = if let [init_index] = *self.move_data.init_path_map[temp_mpi] {
1424                             &self.move_data.inits[init_index]
1425                         } else {
1426                             bug!("temporary should be initialized exactly once")
1427                         };
1428
1429                         let loc = match init.location {
1430                             InitLocation::Statement(stmt) => stmt,
1431                             _ => bug!("temporary initialized in arguments"),
1432                         };
1433
1434                         let body = self.body;
1435                         let bbd = &body[loc.block];
1436                         let stmt = &bbd.statements[loc.statement_index];
1437                         debug!("temporary assigned in: stmt={:?}", stmt);
1438
1439                         if let StatementKind::Assign(box (_, Rvalue::Ref(_, _, source))) = stmt.kind
1440                         {
1441                             propagate_closure_used_mut_place(self, source);
1442                         } else {
1443                             bug!(
1444                                 "closures should only capture user variables \
1445                                  or references to user variables"
1446                             );
1447                         }
1448                     }
1449                     _ => propagate_closure_used_mut_place(self, place),
1450                 }
1451             }
1452             Operand::Constant(..) => {}
1453         }
1454     }
1455
1456     fn consume_operand(
1457         &mut self,
1458         location: Location,
1459         (operand, span): (&'cx Operand<'tcx>, Span),
1460         flow_state: &Flows<'cx, 'tcx>,
1461     ) {
1462         match *operand {
1463             Operand::Copy(place) => {
1464                 // copy of place: check if this is "copy of frozen path"
1465                 // (FIXME: see check_loans.rs)
1466                 self.access_place(
1467                     location,
1468                     (place, span),
1469                     (Deep, Read(ReadKind::Copy)),
1470                     LocalMutationIsAllowed::No,
1471                     flow_state,
1472                 );
1473
1474                 // Finally, check if path was already moved.
1475                 self.check_if_path_or_subpath_is_moved(
1476                     location,
1477                     InitializationRequiringAction::Use,
1478                     (place.as_ref(), span),
1479                     flow_state,
1480                 );
1481             }
1482             Operand::Move(place) => {
1483                 // move of place: check if this is move of already borrowed path
1484                 self.access_place(
1485                     location,
1486                     (place, span),
1487                     (Deep, Write(WriteKind::Move)),
1488                     LocalMutationIsAllowed::Yes,
1489                     flow_state,
1490                 );
1491
1492                 // Finally, check if path was already moved.
1493                 self.check_if_path_or_subpath_is_moved(
1494                     location,
1495                     InitializationRequiringAction::Use,
1496                     (place.as_ref(), span),
1497                     flow_state,
1498                 );
1499             }
1500             Operand::Constant(_) => {}
1501         }
1502     }
1503
1504     /// Checks whether a borrow of this place is invalidated when the function
1505     /// exits
1506     fn check_for_invalidation_at_exit(
1507         &mut self,
1508         location: Location,
1509         borrow: &BorrowData<'tcx>,
1510         span: Span,
1511     ) {
1512         debug!("check_for_invalidation_at_exit({:?})", borrow);
1513         let place = borrow.borrowed_place;
1514         let mut root_place = PlaceRef { local: place.local, projection: &[] };
1515
1516         // FIXME(nll-rfc#40): do more precise destructor tracking here. For now
1517         // we just know that all locals are dropped at function exit (otherwise
1518         // we'll have a memory leak) and assume that all statics have a destructor.
1519         //
1520         // FIXME: allow thread-locals to borrow other thread locals?
1521
1522         let (might_be_alive, will_be_dropped) =
1523             if self.body.local_decls[root_place.local].is_ref_to_thread_local() {
1524                 // Thread-locals might be dropped after the function exits
1525                 // We have to dereference the outer reference because
1526                 // borrows don't conflict behind shared references.
1527                 root_place.projection = DEREF_PROJECTION;
1528                 (true, true)
1529             } else {
1530                 (false, self.locals_are_invalidated_at_exit)
1531             };
1532
1533         if !will_be_dropped {
1534             debug!("place_is_invalidated_at_exit({:?}) - won't be dropped", place);
1535             return;
1536         }
1537
1538         let sd = if might_be_alive { Deep } else { Shallow(None) };
1539
1540         if places_conflict::borrow_conflicts_with_place(
1541             self.infcx.tcx,
1542             &self.body,
1543             place,
1544             borrow.kind,
1545             root_place,
1546             sd,
1547             places_conflict::PlaceConflictBias::Overlap,
1548         ) {
1549             debug!("check_for_invalidation_at_exit({:?}): INVALID", place);
1550             // FIXME: should be talking about the region lifetime instead
1551             // of just a span here.
1552             let span = self.infcx.tcx.sess.source_map().end_point(span);
1553             self.report_borrowed_value_does_not_live_long_enough(
1554                 location,
1555                 borrow,
1556                 (place, span),
1557                 None,
1558             )
1559         }
1560     }
1561
1562     /// Reports an error if this is a borrow of local data.
1563     /// This is called for all Yield expressions on movable generators
1564     fn check_for_local_borrow(&mut self, borrow: &BorrowData<'tcx>, yield_span: Span) {
1565         debug!("check_for_local_borrow({:?})", borrow);
1566
1567         if borrow_of_local_data(borrow.borrowed_place) {
1568             let err = self.cannot_borrow_across_generator_yield(
1569                 self.retrieve_borrow_spans(borrow).var_or_use(),
1570                 yield_span,
1571             );
1572
1573             err.buffer(&mut self.errors_buffer);
1574         }
1575     }
1576
1577     fn check_activations(&mut self, location: Location, span: Span, flow_state: &Flows<'cx, 'tcx>) {
1578         // Two-phase borrow support: For each activation that is newly
1579         // generated at this statement, check if it interferes with
1580         // another borrow.
1581         let borrow_set = self.borrow_set.clone();
1582         for &borrow_index in borrow_set.activations_at_location(location) {
1583             let borrow = &borrow_set[borrow_index];
1584
1585             // only mutable borrows should be 2-phase
1586             assert!(match borrow.kind {
1587                 BorrowKind::Shared | BorrowKind::Shallow => false,
1588                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
1589             });
1590
1591             self.access_place(
1592                 location,
1593                 (borrow.borrowed_place, span),
1594                 (Deep, Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index)),
1595                 LocalMutationIsAllowed::No,
1596                 flow_state,
1597             );
1598             // We do not need to call `check_if_path_or_subpath_is_moved`
1599             // again, as we already called it when we made the
1600             // initial reservation.
1601         }
1602     }
1603
1604     fn check_if_reassignment_to_immutable_state(
1605         &mut self,
1606         location: Location,
1607         local: Local,
1608         place_span: (Place<'tcx>, Span),
1609         flow_state: &Flows<'cx, 'tcx>,
1610     ) {
1611         debug!("check_if_reassignment_to_immutable_state({:?})", local);
1612
1613         // Check if any of the initializiations of `local` have happened yet:
1614         if let Some(init_index) = self.is_local_ever_initialized(local, flow_state) {
1615             // And, if so, report an error.
1616             let init = &self.move_data.inits[init_index];
1617             let span = init.span(&self.body);
1618             self.report_illegal_reassignment(location, place_span, span, place_span.0);
1619         }
1620     }
1621
1622     fn check_if_full_path_is_moved(
1623         &mut self,
1624         location: Location,
1625         desired_action: InitializationRequiringAction,
1626         place_span: (PlaceRef<'tcx>, Span),
1627         flow_state: &Flows<'cx, 'tcx>,
1628     ) {
1629         let maybe_uninits = &flow_state.uninits;
1630
1631         // Bad scenarios:
1632         //
1633         // 1. Move of `a.b.c`, use of `a.b.c`
1634         // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
1635         // 3. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
1636         //    partial initialization support, one might have `a.x`
1637         //    initialized but not `a.b`.
1638         //
1639         // OK scenarios:
1640         //
1641         // 4. Move of `a.b.c`, use of `a.b.d`
1642         // 5. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1643         // 6. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1644         //    must have been initialized for the use to be sound.
1645         // 7. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1646
1647         // The dataflow tracks shallow prefixes distinctly (that is,
1648         // field-accesses on P distinctly from P itself), in order to
1649         // track substructure initialization separately from the whole
1650         // structure.
1651         //
1652         // E.g., when looking at (*a.b.c).d, if the closest prefix for
1653         // which we have a MovePath is `a.b`, then that means that the
1654         // initialization state of `a.b` is all we need to inspect to
1655         // know if `a.b.c` is valid (and from that we infer that the
1656         // dereference and `.d` access is also valid, since we assume
1657         // `a.b.c` is assigned a reference to an initialized and
1658         // well-formed record structure.)
1659
1660         // Therefore, if we seek out the *closest* prefix for which we
1661         // have a MovePath, that should capture the initialization
1662         // state for the place scenario.
1663         //
1664         // This code covers scenarios 1, 2, and 3.
1665
1666         debug!("check_if_full_path_is_moved place: {:?}", place_span.0);
1667         let (prefix, mpi) = self.move_path_closest_to(place_span.0);
1668         if maybe_uninits.contains(mpi) {
1669             self.report_use_of_moved_or_uninitialized(
1670                 location,
1671                 desired_action,
1672                 (prefix, place_span.0, place_span.1),
1673                 mpi,
1674             );
1675         } // Only query longest prefix with a MovePath, not further
1676         // ancestors; dataflow recurs on children when parents
1677         // move (to support partial (re)inits).
1678         //
1679         // (I.e., querying parents breaks scenario 7; but may want
1680         // to do such a query based on partial-init feature-gate.)
1681     }
1682
1683     /// Subslices correspond to multiple move paths, so we iterate through the
1684     /// elements of the base array. For each element we check
1685     ///
1686     /// * Does this element overlap with our slice.
1687     /// * Is any part of it uninitialized.
1688     fn check_if_subslice_element_is_moved(
1689         &mut self,
1690         location: Location,
1691         desired_action: InitializationRequiringAction,
1692         place_span: (PlaceRef<'tcx>, Span),
1693         maybe_uninits: &BitSet<MovePathIndex>,
1694         from: u64,
1695         to: u64,
1696     ) {
1697         if let Some(mpi) = self.move_path_for_place(place_span.0) {
1698             let move_paths = &self.move_data.move_paths;
1699
1700             let root_path = &move_paths[mpi];
1701             for (child_mpi, child_move_path) in root_path.children(move_paths) {
1702                 let last_proj = child_move_path.place.projection.last().unwrap();
1703                 if let ProjectionElem::ConstantIndex { offset, from_end, .. } = last_proj {
1704                     debug_assert!(!from_end, "Array constant indexing shouldn't be `from_end`.");
1705
1706                     if (from..to).contains(offset) {
1707                         let uninit_child =
1708                             self.move_data.find_in_move_path_or_its_descendants(child_mpi, |mpi| {
1709                                 maybe_uninits.contains(mpi)
1710                             });
1711
1712                         if let Some(uninit_child) = uninit_child {
1713                             self.report_use_of_moved_or_uninitialized(
1714                                 location,
1715                                 desired_action,
1716                                 (place_span.0, place_span.0, place_span.1),
1717                                 uninit_child,
1718                             );
1719                             return; // don't bother finding other problems.
1720                         }
1721                     }
1722                 }
1723             }
1724         }
1725     }
1726
1727     fn check_if_path_or_subpath_is_moved(
1728         &mut self,
1729         location: Location,
1730         desired_action: InitializationRequiringAction,
1731         place_span: (PlaceRef<'tcx>, Span),
1732         flow_state: &Flows<'cx, 'tcx>,
1733     ) {
1734         let maybe_uninits = &flow_state.uninits;
1735
1736         // Bad scenarios:
1737         //
1738         // 1. Move of `a.b.c`, use of `a` or `a.b`
1739         //    partial initialization support, one might have `a.x`
1740         //    initialized but not `a.b`.
1741         // 2. All bad scenarios from `check_if_full_path_is_moved`
1742         //
1743         // OK scenarios:
1744         //
1745         // 3. Move of `a.b.c`, use of `a.b.d`
1746         // 4. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
1747         // 5. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
1748         //    must have been initialized for the use to be sound.
1749         // 6. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
1750
1751         self.check_if_full_path_is_moved(location, desired_action, place_span, flow_state);
1752
1753         if let Some((place_base, ProjectionElem::Subslice { from, to, from_end: false })) =
1754             place_span.0.last_projection()
1755         {
1756             let place_ty = place_base.ty(self.body(), self.infcx.tcx);
1757             if let ty::Array(..) = place_ty.ty.kind() {
1758                 self.check_if_subslice_element_is_moved(
1759                     location,
1760                     desired_action,
1761                     (place_base, place_span.1),
1762                     maybe_uninits,
1763                     from,
1764                     to,
1765                 );
1766                 return;
1767             }
1768         }
1769
1770         // A move of any shallow suffix of `place` also interferes
1771         // with an attempt to use `place`. This is scenario 3 above.
1772         //
1773         // (Distinct from handling of scenarios 1+2+4 above because
1774         // `place` does not interfere with suffixes of its prefixes,
1775         // e.g., `a.b.c` does not interfere with `a.b.d`)
1776         //
1777         // This code covers scenario 1.
1778
1779         debug!("check_if_path_or_subpath_is_moved place: {:?}", place_span.0);
1780         if let Some(mpi) = self.move_path_for_place(place_span.0) {
1781             let uninit_mpi = self
1782                 .move_data
1783                 .find_in_move_path_or_its_descendants(mpi, |mpi| maybe_uninits.contains(mpi));
1784
1785             if let Some(uninit_mpi) = uninit_mpi {
1786                 self.report_use_of_moved_or_uninitialized(
1787                     location,
1788                     desired_action,
1789                     (place_span.0, place_span.0, place_span.1),
1790                     uninit_mpi,
1791                 );
1792                 return; // don't bother finding other problems.
1793             }
1794         }
1795     }
1796
1797     /// Currently MoveData does not store entries for all places in
1798     /// the input MIR. For example it will currently filter out
1799     /// places that are Copy; thus we do not track places of shared
1800     /// reference type. This routine will walk up a place along its
1801     /// prefixes, searching for a foundational place that *is*
1802     /// tracked in the MoveData.
1803     ///
1804     /// An Err result includes a tag indicated why the search failed.
1805     /// Currently this can only occur if the place is built off of a
1806     /// static variable, as we do not track those in the MoveData.
1807     fn move_path_closest_to(&mut self, place: PlaceRef<'tcx>) -> (PlaceRef<'tcx>, MovePathIndex) {
1808         match self.move_data.rev_lookup.find(place) {
1809             LookupResult::Parent(Some(mpi)) | LookupResult::Exact(mpi) => {
1810                 (self.move_data.move_paths[mpi].place.as_ref(), mpi)
1811             }
1812             LookupResult::Parent(None) => panic!("should have move path for every Local"),
1813         }
1814     }
1815
1816     fn move_path_for_place(&mut self, place: PlaceRef<'tcx>) -> Option<MovePathIndex> {
1817         // If returns None, then there is no move path corresponding
1818         // to a direct owner of `place` (which means there is nothing
1819         // that borrowck tracks for its analysis).
1820
1821         match self.move_data.rev_lookup.find(place) {
1822             LookupResult::Parent(_) => None,
1823             LookupResult::Exact(mpi) => Some(mpi),
1824         }
1825     }
1826
1827     fn check_if_assigned_path_is_moved(
1828         &mut self,
1829         location: Location,
1830         (place, span): (Place<'tcx>, Span),
1831         flow_state: &Flows<'cx, 'tcx>,
1832     ) {
1833         debug!("check_if_assigned_path_is_moved place: {:?}", place);
1834
1835         // None case => assigning to `x` does not require `x` be initialized.
1836         for (place_base, elem) in place.iter_projections().rev() {
1837             match elem {
1838                 ProjectionElem::Index(_/*operand*/) |
1839                 ProjectionElem::ConstantIndex { .. } |
1840                 // assigning to P[i] requires P to be valid.
1841                 ProjectionElem::Downcast(_/*adt_def*/, _/*variant_idx*/) =>
1842                 // assigning to (P->variant) is okay if assigning to `P` is okay
1843                 //
1844                 // FIXME: is this true even if P is an adt with a dtor?
1845                 { }
1846
1847                 // assigning to (*P) requires P to be initialized
1848                 ProjectionElem::Deref => {
1849                     self.check_if_full_path_is_moved(
1850                         location, InitializationRequiringAction::Use,
1851                         (place_base, span), flow_state);
1852                     // (base initialized; no need to
1853                     // recur further)
1854                     break;
1855                 }
1856
1857                 ProjectionElem::Subslice { .. } => {
1858                     panic!("we don't allow assignments to subslices, location: {:?}",
1859                            location);
1860                 }
1861
1862                 ProjectionElem::Field(..) => {
1863                     // if type of `P` has a dtor, then
1864                     // assigning to `P.f` requires `P` itself
1865                     // be already initialized
1866                     let tcx = self.infcx.tcx;
1867                     let base_ty = place_base.ty(self.body(), tcx).ty;
1868                     match base_ty.kind() {
1869                         ty::Adt(def, _) if def.has_dtor(tcx) => {
1870                             self.check_if_path_or_subpath_is_moved(
1871                                 location, InitializationRequiringAction::Assignment,
1872                                 (place_base, span), flow_state);
1873
1874                             // (base initialized; no need to
1875                             // recur further)
1876                             break;
1877                         }
1878
1879                         // Once `let s; s.x = V; read(s.x);`,
1880                         // is allowed, remove this match arm.
1881                         ty::Adt(..) | ty::Tuple(..) => {
1882                             check_parent_of_field(self, location, place_base, span, flow_state);
1883
1884                             // rust-lang/rust#21232, #54499, #54986: during period where we reject
1885                             // partial initialization, do not complain about unnecessary `mut` on
1886                             // an attempt to do a partial initialization.
1887                             self.used_mut.insert(place.local);
1888                         }
1889
1890                         _ => {}
1891                     }
1892                 }
1893             }
1894         }
1895
1896         fn check_parent_of_field<'cx, 'tcx>(
1897             this: &mut MirBorrowckCtxt<'cx, 'tcx>,
1898             location: Location,
1899             base: PlaceRef<'tcx>,
1900             span: Span,
1901             flow_state: &Flows<'cx, 'tcx>,
1902         ) {
1903             // rust-lang/rust#21232: Until Rust allows reads from the
1904             // initialized parts of partially initialized structs, we
1905             // will, starting with the 2018 edition, reject attempts
1906             // to write to structs that are not fully initialized.
1907             //
1908             // In other words, *until* we allow this:
1909             //
1910             // 1. `let mut s; s.x = Val; read(s.x);`
1911             //
1912             // we will for now disallow this:
1913             //
1914             // 2. `let mut s; s.x = Val;`
1915             //
1916             // and also this:
1917             //
1918             // 3. `let mut s = ...; drop(s); s.x=Val;`
1919             //
1920             // This does not use check_if_path_or_subpath_is_moved,
1921             // because we want to *allow* reinitializations of fields:
1922             // e.g., want to allow
1923             //
1924             // `let mut s = ...; drop(s.x); s.x=Val;`
1925             //
1926             // This does not use check_if_full_path_is_moved on
1927             // `base`, because that would report an error about the
1928             // `base` as a whole, but in this scenario we *really*
1929             // want to report an error about the actual thing that was
1930             // moved, which may be some prefix of `base`.
1931
1932             // Shallow so that we'll stop at any dereference; we'll
1933             // report errors about issues with such bases elsewhere.
1934             let maybe_uninits = &flow_state.uninits;
1935
1936             // Find the shortest uninitialized prefix you can reach
1937             // without going over a Deref.
1938             let mut shortest_uninit_seen = None;
1939             for prefix in this.prefixes(base, PrefixSet::Shallow) {
1940                 let mpi = match this.move_path_for_place(prefix) {
1941                     Some(mpi) => mpi,
1942                     None => continue,
1943                 };
1944
1945                 if maybe_uninits.contains(mpi) {
1946                     debug!(
1947                         "check_parent_of_field updating shortest_uninit_seen from {:?} to {:?}",
1948                         shortest_uninit_seen,
1949                         Some((prefix, mpi))
1950                     );
1951                     shortest_uninit_seen = Some((prefix, mpi));
1952                 } else {
1953                     debug!("check_parent_of_field {:?} is definitely initialized", (prefix, mpi));
1954                 }
1955             }
1956
1957             if let Some((prefix, mpi)) = shortest_uninit_seen {
1958                 // Check for a reassignment into an uninitialized field of a union (for example,
1959                 // after a move out). In this case, do not report an error here. There is an
1960                 // exception, if this is the first assignment into the union (that is, there is
1961                 // no move out from an earlier location) then this is an attempt at initialization
1962                 // of the union - we should error in that case.
1963                 let tcx = this.infcx.tcx;
1964                 if base.ty(this.body(), tcx).ty.is_union() {
1965                     if this.move_data.path_map[mpi].iter().any(|moi| {
1966                         this.move_data.moves[*moi].source.is_predecessor_of(location, this.body)
1967                     }) {
1968                         return;
1969                     }
1970                 }
1971
1972                 this.report_use_of_moved_or_uninitialized(
1973                     location,
1974                     InitializationRequiringAction::PartialAssignment,
1975                     (prefix, base, span),
1976                     mpi,
1977                 );
1978             }
1979         }
1980     }
1981
1982     /// Checks the permissions for the given place and read or write kind
1983     ///
1984     /// Returns `true` if an error is reported.
1985     fn check_access_permissions(
1986         &mut self,
1987         (place, span): (Place<'tcx>, Span),
1988         kind: ReadOrWrite,
1989         is_local_mutation_allowed: LocalMutationIsAllowed,
1990         flow_state: &Flows<'cx, 'tcx>,
1991         location: Location,
1992     ) -> bool {
1993         debug!(
1994             "check_access_permissions({:?}, {:?}, is_local_mutation_allowed: {:?})",
1995             place, kind, is_local_mutation_allowed
1996         );
1997
1998         let error_access;
1999         let the_place_err;
2000
2001         match kind {
2002             Reservation(WriteKind::MutableBorrow(
2003                 borrow_kind @ (BorrowKind::Unique | BorrowKind::Mut { .. }),
2004             ))
2005             | Write(WriteKind::MutableBorrow(
2006                 borrow_kind @ (BorrowKind::Unique | BorrowKind::Mut { .. }),
2007             )) => {
2008                 let is_local_mutation_allowed = match borrow_kind {
2009                     BorrowKind::Unique => LocalMutationIsAllowed::Yes,
2010                     BorrowKind::Mut { .. } => is_local_mutation_allowed,
2011                     BorrowKind::Shared | BorrowKind::Shallow => unreachable!(),
2012                 };
2013                 match self.is_mutable(place.as_ref(), is_local_mutation_allowed) {
2014                     Ok(root_place) => {
2015                         self.add_used_mut(root_place, flow_state);
2016                         return false;
2017                     }
2018                     Err(place_err) => {
2019                         error_access = AccessKind::MutableBorrow;
2020                         the_place_err = place_err;
2021                     }
2022                 }
2023             }
2024             Reservation(WriteKind::Mutate) | Write(WriteKind::Mutate) => {
2025                 match self.is_mutable(place.as_ref(), is_local_mutation_allowed) {
2026                     Ok(root_place) => {
2027                         self.add_used_mut(root_place, flow_state);
2028                         return false;
2029                     }
2030                     Err(place_err) => {
2031                         error_access = AccessKind::Mutate;
2032                         the_place_err = place_err;
2033                     }
2034                 }
2035             }
2036
2037             Reservation(
2038                 WriteKind::Move
2039                 | WriteKind::StorageDeadOrDrop
2040                 | WriteKind::MutableBorrow(BorrowKind::Shared)
2041                 | WriteKind::MutableBorrow(BorrowKind::Shallow),
2042             )
2043             | Write(
2044                 WriteKind::Move
2045                 | WriteKind::StorageDeadOrDrop
2046                 | WriteKind::MutableBorrow(BorrowKind::Shared)
2047                 | WriteKind::MutableBorrow(BorrowKind::Shallow),
2048             ) => {
2049                 if let (Err(_), true) = (
2050                     self.is_mutable(place.as_ref(), is_local_mutation_allowed),
2051                     self.errors_buffer.is_empty(),
2052                 ) {
2053                     // rust-lang/rust#46908: In pure NLL mode this code path should be
2054                     // unreachable, but we use `delay_span_bug` because we can hit this when
2055                     // dereferencing a non-Copy raw pointer *and* have `-Ztreat-err-as-bug`
2056                     // enabled. We don't want to ICE for that case, as other errors will have
2057                     // been emitted (#52262).
2058                     self.infcx.tcx.sess.delay_span_bug(
2059                         span,
2060                         &format!(
2061                             "Accessing `{:?}` with the kind `{:?}` shouldn't be possible",
2062                             place, kind,
2063                         ),
2064                     );
2065                 }
2066                 return false;
2067             }
2068             Activation(..) => {
2069                 // permission checks are done at Reservation point.
2070                 return false;
2071             }
2072             Read(
2073                 ReadKind::Borrow(
2074                     BorrowKind::Unique
2075                     | BorrowKind::Mut { .. }
2076                     | BorrowKind::Shared
2077                     | BorrowKind::Shallow,
2078                 )
2079                 | ReadKind::Copy,
2080             ) => {
2081                 // Access authorized
2082                 return false;
2083             }
2084         }
2085
2086         // rust-lang/rust#21232, #54986: during period where we reject
2087         // partial initialization, do not complain about mutability
2088         // errors except for actual mutation (as opposed to an attempt
2089         // to do a partial initialization).
2090         let previously_initialized =
2091             self.is_local_ever_initialized(place.local, flow_state).is_some();
2092
2093         // at this point, we have set up the error reporting state.
2094         if previously_initialized {
2095             self.report_mutability_error(place, span, the_place_err, error_access, location);
2096             true
2097         } else {
2098             false
2099         }
2100     }
2101
2102     fn is_local_ever_initialized(
2103         &self,
2104         local: Local,
2105         flow_state: &Flows<'cx, 'tcx>,
2106     ) -> Option<InitIndex> {
2107         let mpi = self.move_data.rev_lookup.find_local(local);
2108         let ii = &self.move_data.init_path_map[mpi];
2109         for &index in ii {
2110             if flow_state.ever_inits.contains(index) {
2111                 return Some(index);
2112             }
2113         }
2114         None
2115     }
2116
2117     /// Adds the place into the used mutable variables set
2118     fn add_used_mut(&mut self, root_place: RootPlace<'tcx>, flow_state: &Flows<'cx, 'tcx>) {
2119         match root_place {
2120             RootPlace { place_local: local, place_projection: [], is_local_mutation_allowed } => {
2121                 // If the local may have been initialized, and it is now currently being
2122                 // mutated, then it is justified to be annotated with the `mut`
2123                 // keyword, since the mutation may be a possible reassignment.
2124                 if is_local_mutation_allowed != LocalMutationIsAllowed::Yes
2125                     && self.is_local_ever_initialized(local, flow_state).is_some()
2126                 {
2127                     self.used_mut.insert(local);
2128                 }
2129             }
2130             RootPlace {
2131                 place_local: _,
2132                 place_projection: _,
2133                 is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
2134             } => {}
2135             RootPlace {
2136                 place_local,
2137                 place_projection: place_projection @ [.., _],
2138                 is_local_mutation_allowed: _,
2139             } => {
2140                 if let Some(field) = self.is_upvar_field_projection(PlaceRef {
2141                     local: place_local,
2142                     projection: place_projection,
2143                 }) {
2144                     self.used_mut_upvars.push(field);
2145                 }
2146             }
2147         }
2148     }
2149
2150     /// Whether this value can be written or borrowed mutably.
2151     /// Returns the root place if the place passed in is a projection.
2152     fn is_mutable(
2153         &self,
2154         place: PlaceRef<'tcx>,
2155         is_local_mutation_allowed: LocalMutationIsAllowed,
2156     ) -> Result<RootPlace<'tcx>, PlaceRef<'tcx>> {
2157         debug!("is_mutable: place={:?}, is_local...={:?}", place, is_local_mutation_allowed);
2158         match place.last_projection() {
2159             None => {
2160                 let local = &self.body.local_decls[place.local];
2161                 match local.mutability {
2162                     Mutability::Not => match is_local_mutation_allowed {
2163                         LocalMutationIsAllowed::Yes => Ok(RootPlace {
2164                             place_local: place.local,
2165                             place_projection: place.projection,
2166                             is_local_mutation_allowed: LocalMutationIsAllowed::Yes,
2167                         }),
2168                         LocalMutationIsAllowed::ExceptUpvars => Ok(RootPlace {
2169                             place_local: place.local,
2170                             place_projection: place.projection,
2171                             is_local_mutation_allowed: LocalMutationIsAllowed::ExceptUpvars,
2172                         }),
2173                         LocalMutationIsAllowed::No => Err(place),
2174                     },
2175                     Mutability::Mut => Ok(RootPlace {
2176                         place_local: place.local,
2177                         place_projection: place.projection,
2178                         is_local_mutation_allowed,
2179                     }),
2180                 }
2181             }
2182             Some((place_base, elem)) => {
2183                 match elem {
2184                     ProjectionElem::Deref => {
2185                         let base_ty = place_base.ty(self.body(), self.infcx.tcx).ty;
2186
2187                         // Check the kind of deref to decide
2188                         match base_ty.kind() {
2189                             ty::Ref(_, _, mutbl) => {
2190                                 match mutbl {
2191                                     // Shared borrowed data is never mutable
2192                                     hir::Mutability::Not => Err(place),
2193                                     // Mutably borrowed data is mutable, but only if we have a
2194                                     // unique path to the `&mut`
2195                                     hir::Mutability::Mut => {
2196                                         let mode = match self.is_upvar_field_projection(place) {
2197                                             Some(field) if self.upvars[field.index()].by_ref => {
2198                                                 is_local_mutation_allowed
2199                                             }
2200                                             _ => LocalMutationIsAllowed::Yes,
2201                                         };
2202
2203                                         self.is_mutable(place_base, mode)
2204                                     }
2205                                 }
2206                             }
2207                             ty::RawPtr(tnm) => {
2208                                 match tnm.mutbl {
2209                                     // `*const` raw pointers are not mutable
2210                                     hir::Mutability::Not => Err(place),
2211                                     // `*mut` raw pointers are always mutable, regardless of
2212                                     // context. The users have to check by themselves.
2213                                     hir::Mutability::Mut => Ok(RootPlace {
2214                                         place_local: place.local,
2215                                         place_projection: place.projection,
2216                                         is_local_mutation_allowed,
2217                                     }),
2218                                 }
2219                             }
2220                             // `Box<T>` owns its content, so mutable if its location is mutable
2221                             _ if base_ty.is_box() => {
2222                                 self.is_mutable(place_base, is_local_mutation_allowed)
2223                             }
2224                             // Deref should only be for reference, pointers or boxes
2225                             _ => bug!("Deref of unexpected type: {:?}", base_ty),
2226                         }
2227                     }
2228                     // All other projections are owned by their base path, so mutable if
2229                     // base path is mutable
2230                     ProjectionElem::Field(..)
2231                     | ProjectionElem::Index(..)
2232                     | ProjectionElem::ConstantIndex { .. }
2233                     | ProjectionElem::Subslice { .. }
2234                     | ProjectionElem::Downcast(..) => {
2235                         let upvar_field_projection = self.is_upvar_field_projection(place);
2236                         if let Some(field) = upvar_field_projection {
2237                             let upvar = &self.upvars[field.index()];
2238                             debug!(
2239                                 "is_mutable: upvar.mutability={:?} local_mutation_is_allowed={:?} \
2240                                  place={:?}, place_base={:?}",
2241                                 upvar, is_local_mutation_allowed, place, place_base
2242                             );
2243                             match (upvar.place.mutability, is_local_mutation_allowed) {
2244                                 (
2245                                     Mutability::Not,
2246                                     LocalMutationIsAllowed::No
2247                                     | LocalMutationIsAllowed::ExceptUpvars,
2248                                 ) => Err(place),
2249                                 (Mutability::Not, LocalMutationIsAllowed::Yes)
2250                                 | (Mutability::Mut, _) => {
2251                                     // Subtle: this is an upvar
2252                                     // reference, so it looks like
2253                                     // `self.foo` -- we want to double
2254                                     // check that the location `*self`
2255                                     // is mutable (i.e., this is not a
2256                                     // `Fn` closure).  But if that
2257                                     // check succeeds, we want to
2258                                     // *blame* the mutability on
2259                                     // `place` (that is,
2260                                     // `self.foo`). This is used to
2261                                     // propagate the info about
2262                                     // whether mutability declarations
2263                                     // are used outwards, so that we register
2264                                     // the outer variable as mutable. Otherwise a
2265                                     // test like this fails to record the `mut`
2266                                     // as needed:
2267                                     //
2268                                     // ```
2269                                     // fn foo<F: FnOnce()>(_f: F) { }
2270                                     // fn main() {
2271                                     //     let var = Vec::new();
2272                                     //     foo(move || {
2273                                     //         var.push(1);
2274                                     //     });
2275                                     // }
2276                                     // ```
2277                                     let _ =
2278                                         self.is_mutable(place_base, is_local_mutation_allowed)?;
2279                                     Ok(RootPlace {
2280                                         place_local: place.local,
2281                                         place_projection: place.projection,
2282                                         is_local_mutation_allowed,
2283                                     })
2284                                 }
2285                             }
2286                         } else {
2287                             self.is_mutable(place_base, is_local_mutation_allowed)
2288                         }
2289                     }
2290                 }
2291             }
2292         }
2293     }
2294
2295     /// If `place` is a field projection, and the field is being projected from a closure type,
2296     /// then returns the index of the field being projected. Note that this closure will always
2297     /// be `self` in the current MIR, because that is the only time we directly access the fields
2298     /// of a closure type.
2299     fn is_upvar_field_projection(&self, place_ref: PlaceRef<'tcx>) -> Option<Field> {
2300         path_utils::is_upvar_field_projection(self.infcx.tcx, &self.upvars, place_ref, self.body())
2301     }
2302 }
2303
2304 /// The degree of overlap between 2 places for borrow-checking.
2305 enum Overlap {
2306     /// The places might partially overlap - in this case, we give
2307     /// up and say that they might conflict. This occurs when
2308     /// different fields of a union are borrowed. For example,
2309     /// if `u` is a union, we have no way of telling how disjoint
2310     /// `u.a.x` and `a.b.y` are.
2311     Arbitrary,
2312     /// The places have the same type, and are either completely disjoint
2313     /// or equal - i.e., they can't "partially" overlap as can occur with
2314     /// unions. This is the "base case" on which we recur for extensions
2315     /// of the place.
2316     EqualOrDisjoint,
2317     /// The places are disjoint, so we know all extensions of them
2318     /// will also be disjoint.
2319     Disjoint,
2320 }