src/librustc_mir/dataflow/impls/borrows.rs

   1 // Copyright 2012-2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc;
  12 use rustc::hir;
  13 use rustc::hir::def_id::DefId;
  14 use rustc::middle::region;
  15 use rustc::mir::{self, Location, Place, Mir};
  16 use rustc::mir::visit::{PlaceContext, Visitor};
  17 use rustc::ty::{self, Region, TyCtxt};
  18 use rustc::ty::RegionKind;
  19 use rustc::ty::RegionKind::ReScope;
  20 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  21
  22 use rustc_data_structures::bitslice::{BitwiseOperator};
  23 use rustc_data_structures::indexed_set::{IdxSet};
  24 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  25
  26 use dataflow::{BitDenotation, BlockSets, InitialFlow};
  27 pub use dataflow::indexes::{BorrowIndex, ReserveOrActivateIndex};
  28 use borrow_check::nll::region_infer::RegionInferenceContext;
  29 use borrow_check::nll::ToRegionVid;
  30
  31 use syntax_pos::Span;
  32
  33 use std::fmt;
  34 use std::hash::Hash;
  35 use std::rc::Rc;
  36
  37 /// `Borrows` stores the data used in the analyses that track the flow
  38 /// of borrows.
  39 ///
  40 /// It uniquely identifies every borrow (`Rvalue::Ref`) by a
  41 /// `BorrowIndex`, and maps each such index to a `BorrowData`
  42 /// describing the borrow. These indexes are used for representing the
  43 /// borrows in compact bitvectors.
  44 pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
  45     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  46     mir: &'a Mir<'tcx>,
  47     scope_tree: Rc<region::ScopeTree>,
  48     root_scope: Option<region::Scope>,
  49
  50     /// The fundamental map relating bitvector indexes to the borrows
  51     /// in the MIR.
  52     borrows: IndexVec<BorrowIndex, BorrowData<'tcx>>,
  53
  54     /// Each borrow is also uniquely identified in the MIR by the
  55     /// `Location` of the assignment statement in which it appears on
  56     /// the right hand side; we map each such location to the
  57     /// corresponding `BorrowIndex`.
  58     location_map: FxHashMap<Location, BorrowIndex>,
  59
  60     /// Every borrow in MIR is immediately stored into a place via an
  61     /// assignment statement. This maps each such assigned place back
  62     /// to its borrow-indexes.
  63     assigned_map: FxHashMap<Place<'tcx>, FxHashSet<BorrowIndex>>,
  64
  65     /// Every borrow has a region; this maps each such regions back to
  66     /// its borrow-indexes.
  67     region_map: FxHashMap<Region<'tcx>, FxHashSet<BorrowIndex>>,
  68     local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
  69     region_span_map: FxHashMap<RegionKind, Span>,
  70     nonlexical_regioncx: Option<Rc<RegionInferenceContext<'tcx>>>,
  71 }
  72
  73 // Two-phase borrows actually requires two flow analyses; they need
  74 // to be separate because the final results of the first are used to
  75 // construct the gen+kill sets for the second. (The dataflow system
  76 // is not designed to allow the gen/kill sets to change during the
  77 // fixed-point iteration.)
  78
  79 /// The `Reservations` analysis is the first of the two flow analyses
  80 /// tracking (phased) borrows. It computes where a borrow is reserved;
  81 /// i.e. where it can reach in the control flow starting from its
  82 /// initial `assigned = &'rgn borrowed` statement, and ending
  83 /// whereever `'rgn` itself ends.
  84 pub(crate) struct Reservations<'a, 'gcx: 'tcx, 'tcx: 'a>(pub(crate) Borrows<'a, 'gcx, 'tcx>);
  85
  86 /// The `ActiveBorrows` analysis is the second of the two flow
  87 /// analyses tracking (phased) borrows. It computes where any given
  88 /// borrow `&assigned = &'rgn borrowed` is *active*, which starts at
  89 /// the first use of `assigned` after the reservation has started, and
  90 /// ends whereever `'rgn` itself ends.
  91 pub(crate) struct ActiveBorrows<'a, 'gcx: 'tcx, 'tcx: 'a>(pub(crate) Borrows<'a, 'gcx, 'tcx>);
  92
  93 impl<'a, 'gcx, 'tcx> Reservations<'a, 'gcx, 'tcx> {
  94     pub(crate) fn new(b: Borrows<'a, 'gcx, 'tcx>) -> Self { Reservations(b) }
  95     pub(crate) fn location(&self, idx: ReserveOrActivateIndex) -> &Location {
  96         self.0.location(idx.borrow_index())
  97     }
  98 }
  99
 100 impl<'a, 'gcx, 'tcx> ActiveBorrows<'a, 'gcx, 'tcx> {
 101     pub(crate) fn new(r: Reservations<'a, 'gcx, 'tcx>) -> Self { ActiveBorrows(r.0) }
 102     pub(crate) fn location(&self, idx: ReserveOrActivateIndex) -> &Location {
 103         self.0.location(idx.borrow_index())
 104     }
 105 }
 106
 107 // temporarily allow some dead fields: `kind` and `region` will be
 108 // needed by borrowck; `borrowed_place` will probably be a MovePathIndex when
 109 // that is extended to include borrowed data paths.
 110 #[allow(dead_code)]
 111 #[derive(Debug)]
 112 pub struct BorrowData<'tcx> {
 113     pub(crate) location: Location,
 114     pub(crate) kind: mir::BorrowKind,
 115     pub(crate) region: Region<'tcx>,
 116     pub(crate) borrowed_place: mir::Place<'tcx>,
 117     pub(crate) assigned_place: mir::Place<'tcx>,
 118 }
 119
 120 impl<'tcx> fmt::Display for BorrowData<'tcx> {
 121     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
 122         let kind = match self.kind {
 123             mir::BorrowKind::Shared => "",
 124             mir::BorrowKind::Unique => "uniq ",
 125             mir::BorrowKind::Mut => "mut ",
 126         };
 127         let region = format!("{}", self.region);
 128         let region = if region.len() > 0 { format!("{} ", region) } else { region };
 129         write!(w, "&{}{}{:?}", region, kind, self.borrowed_place)
 130     }
 131 }
 132
 133 impl ReserveOrActivateIndex {
 134     fn reserved(i: BorrowIndex) -> Self { ReserveOrActivateIndex::new(i.index() * 2) }
 135     fn active(i: BorrowIndex) -> Self { ReserveOrActivateIndex::new((i.index() * 2) + 1) }
 136
 137     pub(crate) fn is_reservation(self) -> bool { self.index() % 2 == 0 }
 138     pub(crate) fn is_activation(self) -> bool { self.index() % 2 == 1}
 139
 140     pub(crate) fn kind(self) -> &'static str {
 141         if self.is_reservation() { "reserved" } else { "active" }
 142     }
 143     pub(crate) fn borrow_index(self) -> BorrowIndex {
 144         BorrowIndex::new(self.index() / 2)
 145     }
 146 }
 147
 148 impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
 149     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 150                mir: &'a Mir<'tcx>,
 151                nonlexical_regioncx: Option<Rc<RegionInferenceContext<'tcx>>>,
 152                def_id: DefId,
 153                body_id: Option<hir::BodyId>)
 154                -> Self {
 155         let scope_tree = tcx.region_scope_tree(def_id);
 156         let root_scope = body_id.map(|body_id| {
 157             region::Scope::CallSite(tcx.hir.body(body_id).value.hir_id.local_id)
 158         });
 159         let mut visitor = GatherBorrows {
 160             tcx,
 161             mir,
 162             idx_vec: IndexVec::new(),
 163             location_map: FxHashMap(),
 164             assigned_map: FxHashMap(),
 165             region_map: FxHashMap(),
 166             local_map: FxHashMap(),
 167             region_span_map: FxHashMap()
 168         };
 169         visitor.visit_mir(mir);
 170         return Borrows { tcx: tcx,
 171                          mir: mir,
 172                          borrows: visitor.idx_vec,
 173                          scope_tree,
 174                          root_scope,
 175                          location_map: visitor.location_map,
 176                          assigned_map: visitor.assigned_map,
 177                          region_map: visitor.region_map,
 178                          local_map: visitor.local_map,
 179                          region_span_map: visitor.region_span_map,
 180                          nonlexical_regioncx };
 181
 182         struct GatherBorrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
 183             tcx: TyCtxt<'a, 'gcx, 'tcx>,
 184             mir: &'a Mir<'tcx>,
 185             idx_vec: IndexVec<BorrowIndex, BorrowData<'tcx>>,
 186             location_map: FxHashMap<Location, BorrowIndex>,
 187             assigned_map: FxHashMap<Place<'tcx>, FxHashSet<BorrowIndex>>,
 188             region_map: FxHashMap<Region<'tcx>, FxHashSet<BorrowIndex>>,
 189             local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
 190             region_span_map: FxHashMap<RegionKind, Span>,
 191         }
 192
 193         impl<'a, 'gcx, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'gcx, 'tcx> {
 194             fn visit_assign(&mut self,
 195                             block: mir::BasicBlock,
 196                             assigned_place: &mir::Place<'tcx>,
 197                             rvalue: &mir::Rvalue<'tcx>,
 198                             location: mir::Location) {
 199                 fn root_local(mut p: &mir::Place<'_>) -> Option<mir::Local> {
 200                     loop { match p {
 201                         mir::Place::Projection(pi) => p = &pi.base,
 202                         mir::Place::Static(_) => return None,
 203                         mir::Place::Local(l) => return Some(*l)
 204                     }}
 205                 }
 206
 207                 if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue {
 208                     if is_unsafe_place(self.tcx, self.mir, borrowed_place) { return; }
 209
 210                     let borrow = BorrowData {
 211                         location, kind, region,
 212                         borrowed_place: borrowed_place.clone(),
 213                         assigned_place: assigned_place.clone(),
 214                     };
 215                     let idx = self.idx_vec.push(borrow);
 216                     self.location_map.insert(location, idx);
 217
 218                     insert(&mut self.assigned_map, assigned_place, idx);
 219                     insert(&mut self.region_map, &region, idx);
 220                     if let Some(local) = root_local(borrowed_place) {
 221                         insert(&mut self.local_map, &local, idx);
 222                     }
 223                 }
 224
 225                 return self.super_assign(block, assigned_place, rvalue, location);
 226
 227                 fn insert<'a, K, V>(map: &'a mut FxHashMap<K, FxHashSet<V>>,
 228                                     k: &K,
 229                                     v: V)
 230                     where K: Clone+Eq+Hash, V: Eq+Hash
 231                 {
 232                     map.entry(k.clone())
 233                         .or_insert(FxHashSet())
 234                         .insert(v);
 235                 }
 236             }
 237
 238             fn visit_rvalue(&mut self,
 239                             rvalue: &mir::Rvalue<'tcx>,
 240                             location: mir::Location) {
 241                 if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue {
 242                     // double-check that we already registered a BorrowData for this
 243
 244                     let mut found_it = false;
 245                     for idx in &self.region_map[region] {
 246                         let bd = &self.idx_vec[*idx];
 247                         if bd.location == location &&
 248                             bd.kind == kind &&
 249                             bd.region == region &&
 250                             bd.borrowed_place == *place
 251                         {
 252                             found_it = true;
 253                             break;
 254                         }
 255                     }
 256                     assert!(found_it, "Ref {:?} at {:?} missing BorrowData", rvalue, location);
 257                 }
 258
 259                 return self.super_rvalue(rvalue, location);
 260             }
 261
 262             fn visit_statement(&mut self,
 263                                block: mir::BasicBlock,
 264                                statement: &mir::Statement<'tcx>,
 265                                location: Location) {
 266                 if let mir::StatementKind::EndRegion(region_scope) = statement.kind {
 267                     self.region_span_map.insert(ReScope(region_scope), statement.source_info.span);
 268                 }
 269                 return self.super_statement(block, statement, location);
 270             }
 271         }
 272     }
 273
 274     pub fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrows }
 275
 276     pub fn scope_tree(&self) -> &Rc<region::ScopeTree> { &self.scope_tree }
 277
 278     pub fn location(&self, idx: BorrowIndex) -> &Location {
 279         &self.borrows[idx].location
 280     }
 281
 282     /// Add all borrows to the kill set, if those borrows are out of scope at `location`.
 283     ///
 284     /// `is_activations` tracks whether we are in the Reservations or
 285     /// the ActiveBorrows flow analysis, and does not set the
 286     /// activation kill bits in the former case. (Technically, we
 287     /// could set those kill bits without such a guard, since they are
 288     /// never gen'ed by Reservations in the first place.  But it makes
 289     /// the instrumentation and graph renderings nicer to leave
 290     /// activations out when of the Reservations kill sets.)
 291     fn kill_loans_out_of_scope_at_location(&self,
 292                                            sets: &mut BlockSets<ReserveOrActivateIndex>,
 293                                            location: Location,
 294                                            is_activations: bool) {
 295         if let Some(ref regioncx) = self.nonlexical_regioncx {
 296             // NOTE: The state associated with a given `location`
 297             // reflects the dataflow on entry to the statement. If it
 298             // does not contain `borrow_region`, then then that means
 299             // that the statement at `location` kills the borrow.
 300             //
 301             // We are careful always to call this function *before* we
 302             // set up the gen-bits for the statement or
 303             // termanator. That way, if the effect of the statement or
 304             // terminator *does* introduce a new loan of the same
 305             // region, then setting that gen-bit will override any
 306             // potential kill introduced here.
 307             for (borrow_index, borrow_data) in self.borrows.iter_enumerated() {
 308                 let borrow_region = borrow_data.region.to_region_vid();
 309                 if !regioncx.region_contains_point(borrow_region, location) {
 310                     sets.kill(&ReserveOrActivateIndex::reserved(borrow_index));
 311                     if is_activations {
 312                         sets.kill(&ReserveOrActivateIndex::active(borrow_index));
 313                     }
 314                 }
 315             }
 316         }
 317     }
 318
 319     /// Models statement effect in Reservations and ActiveBorrows flow
 320     /// analyses; `is activations` tells us if we are in the latter
 321     /// case.
 322     fn statement_effect_on_borrows(&self,
 323                                    sets: &mut BlockSets<ReserveOrActivateIndex>,
 324                                    location: Location,
 325                                    is_activations: bool) {
 326         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 327             panic!("could not find block at location {:?}", location);
 328         });
 329         let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| {
 330             panic!("could not find statement at location {:?}");
 331         });
 332
 333         // Do kills introduced by NLL before setting up any potential
 334         // gens. (See NOTE in kill_loans_out_of_scope_at_location.)
 335         self.kill_loans_out_of_scope_at_location(sets, location, is_activations);
 336
 337         if is_activations {
 338             // INVARIANT: `sets.on_entry` accurately captures
 339             // reservations on entry to statement (b/c
 340             // accumulates_intrablock_state is overridden for
 341             // ActiveBorrows).
 342             //
 343             // Now compute the activations generated by uses within
 344             // the statement based on that reservation state.
 345             let mut find = FindPlaceUses { sets, assigned_map: &self.assigned_map };
 346             find.visit_statement(location.block, stmt, location);
 347         }
 348
 349         match stmt.kind {
 350             // EndRegion kills any borrows (reservations and active borrows both)
 351             mir::StatementKind::EndRegion(region_scope) => {
 352                 if let Some(borrow_indexes) = self.region_map.get(&ReScope(region_scope)) {
 353                     assert!(self.nonlexical_regioncx.is_none());
 354                     for idx in borrow_indexes {
 355                         sets.kill(&ReserveOrActivateIndex::reserved(*idx));
 356                         if is_activations {
 357                             sets.kill(&ReserveOrActivateIndex::active(*idx));
 358                         }
 359                     }
 360                 } else {
 361                     // (if there is no entry, then there are no borrows to be tracked)
 362                 }
 363             }
 364
 365             mir::StatementKind::Assign(ref lhs, ref rhs) => {
 366                 // Make sure there are no remaining borrows for variables
 367                 // that are assigned over.
 368                 if let Place::Local(ref local) = *lhs {
 369                     // FIXME: Handle the case in which we're assigning over
 370                     // a projection (`foo.bar`).
 371                     self.kill_borrows_on_local(sets, local, is_activations);
 372                 }
 373
 374                 // NOTE: if/when the Assign case is revised to inspect
 375                 // the assigned_place here, make sure to also
 376                 // re-consider the current implementations of the
 377                 // propagate_call_return method.
 378
 379                 if let mir::Rvalue::Ref(region, _, ref place) = *rhs {
 380                     if is_unsafe_place(self.tcx, self.mir, place) { return; }
 381                     if let RegionKind::ReEmpty = region {
 382                         // If the borrowed value is dead, the region for it
 383                         // can be empty. Don't track the borrow in that case.
 384                         return
 385                     }
 386
 387                     let index = self.location_map.get(&location).unwrap_or_else(|| {
 388                         panic!("could not find BorrowIndex for location {:?}", location);
 389                     });
 390                     assert!(self.region_map.get(region).unwrap_or_else(|| {
 391                         panic!("could not find BorrowIndexs for region {:?}", region);
 392                     }).contains(&index));
 393                     sets.gen(&ReserveOrActivateIndex::reserved(*index));
 394
 395                     if is_activations {
 396                         // Issue #46746: Two-phase borrows handles
 397                         // stmts of form `Tmp = &mut Borrow` ...
 398                         match lhs {
 399                             Place::Local(..) => {} // okay
 400                             Place::Static(..) => unreachable!(), // (filtered by is_unsafe_place)
 401                             Place::Projection(..) => {
 402                                 // ... can assign into projections,
 403                                 // e.g. `box (&mut _)`. Current
 404                                 // conservative solution: force
 405                                 // immediate activation here.
 406                                 sets.gen(&ReserveOrActivateIndex::active(*index));
 407                             }
 408                         }
 409                     }
 410                 }
 411             }
 412
 413             mir::StatementKind::StorageDead(local) => {
 414                 // Make sure there are no remaining borrows for locals that
 415                 // are gone out of scope.
 416                 self.kill_borrows_on_local(sets, &local, is_activations)
 417             }
 418
 419             mir::StatementKind::InlineAsm { ref outputs, ref asm, .. } => {
 420                 for (output, kind) in outputs.iter().zip(&asm.outputs) {
 421                     if !kind.is_indirect && !kind.is_rw {
 422                         // Make sure there are no remaining borrows for direct
 423                         // output variables.
 424                         if let Place::Local(ref local) = *output {
 425                             // FIXME: Handle the case in which we're assigning over
 426                             // a projection (`foo.bar`).
 427                             self.kill_borrows_on_local(sets, local, is_activations);
 428                         }
 429                     }
 430                 }
 431             }
 432
 433             mir::StatementKind::SetDiscriminant { .. } |
 434             mir::StatementKind::StorageLive(..) |
 435             mir::StatementKind::Validate(..) |
 436             mir::StatementKind::Nop => {}
 437
 438         }
 439     }
 440
 441     fn kill_borrows_on_local(&self,
 442                              sets: &mut BlockSets<ReserveOrActivateIndex>,
 443                              local: &rustc::mir::Local,
 444                              is_activations: bool)
 445     {
 446         if let Some(borrow_indexes) = self.local_map.get(local) {
 447             sets.kill_all(borrow_indexes.iter()
 448                             .map(|b| ReserveOrActivateIndex::reserved(*b)));
 449             if is_activations {
 450                 sets.kill_all(borrow_indexes.iter()
 451                                 .map(|b| ReserveOrActivateIndex::active(*b)));
 452             }
 453         }
 454     }
 455
 456     /// Models terminator effect in Reservations and ActiveBorrows
 457     /// flow analyses; `is activations` tells us if we are in the
 458     /// latter case.
 459     fn terminator_effect_on_borrows(&self,
 460                                     sets: &mut BlockSets<ReserveOrActivateIndex>,
 461                                     location: Location,
 462                                     is_activations: bool) {
 463         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 464             panic!("could not find block at location {:?}", location);
 465         });
 466
 467         // Do kills introduced by NLL before setting up any potential
 468         // gens. (See NOTE in kill_loans_out_of_scope_at_location.)
 469         self.kill_loans_out_of_scope_at_location(sets, location, is_activations);
 470
 471         let term = block.terminator();
 472         if is_activations {
 473             // INVARIANT: `sets.on_entry` accurately captures
 474             // reservations on entry to terminator (b/c
 475             // accumulates_intrablock_state is overridden for
 476             // ActiveBorrows).
 477             //
 478             // Now compute effect of the terminator on the activations
 479             // themselves in the ActiveBorrows state.
 480             let mut find = FindPlaceUses { sets, assigned_map: &self.assigned_map };
 481             find.visit_terminator(location.block, term, location);
 482         }
 483
 484         match term.kind {
 485             mir::TerminatorKind::Resume |
 486             mir::TerminatorKind::Return |
 487             mir::TerminatorKind::GeneratorDrop => {
 488                 // When we return from the function, then all `ReScope`-style regions
 489                 // are guaranteed to have ended.
 490                 // Normally, there would be `EndRegion` statements that come before,
 491                 // and hence most of these loans will already be dead -- but, in some cases
 492                 // like unwind paths, we do not always emit `EndRegion` statements, so we
 493                 // add some kills here as a "backup" and to avoid spurious error messages.
 494                 for (borrow_index, borrow_data) in self.borrows.iter_enumerated() {
 495                     if let ReScope(scope) = borrow_data.region {
 496                         // Check that the scope is not actually a scope from a function that is
 497                         // a parent of our closure. Note that the CallSite scope itself is
 498                         // *outside* of the closure, for some weird reason.
 499                         if let Some(root_scope) = self.root_scope {
 500                             if *scope != root_scope &&
 501                                 self.scope_tree.is_subscope_of(*scope, root_scope)
 502                             {
 503                                 sets.kill(&ReserveOrActivateIndex::reserved(borrow_index));
 504                                 if is_activations {
 505                                     sets.kill(&ReserveOrActivateIndex::active(borrow_index));
 506                                 }
 507                             }
 508                         }
 509                     }
 510                 }
 511             }
 512             mir::TerminatorKind::Abort |
 513             mir::TerminatorKind::SwitchInt {..} |
 514             mir::TerminatorKind::Drop {..} |
 515             mir::TerminatorKind::DropAndReplace {..} |
 516             mir::TerminatorKind::Call {..} |
 517             mir::TerminatorKind::Assert {..} |
 518             mir::TerminatorKind::Yield {..} |
 519             mir::TerminatorKind::Goto {..} |
 520             mir::TerminatorKind::FalseEdges {..} |
 521             mir::TerminatorKind::Unreachable => {}
 522         }
 523     }
 524 }
 525
 526 impl<'a, 'gcx, 'tcx> ActiveBorrows<'a, 'gcx, 'tcx> {
 527     pub(crate) fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> {
 528         self.0.borrows()
 529     }
 530
 531     /// Returns the span for the "end point" given region. This will
 532     /// return `None` if NLL is enabled, since that concept has no
 533     /// meaning there.  Otherwise, return region span if it exists and
 534     /// span for end of the function if it doesn't exist.
 535     pub(crate) fn opt_region_end_span(&self, region: &Region) -> Option<Span> {
 536         match self.0.nonlexical_regioncx {
 537             Some(_) => None,
 538             None => {
 539                 match self.0.region_span_map.get(region) {
 540                     Some(span) => Some(self.0.tcx.sess.codemap().end_point(*span)),
 541                     None => Some(self.0.tcx.sess.codemap().end_point(self.0.mir.span))
 542                 }
 543             }
 544         }
 545     }
 546 }
 547
 548 /// `FindPlaceUses` is a MIR visitor that updates `self.sets` for all
 549 /// of the borrows activated by a given statement or terminator.
 550 ///
 551 /// ----
 552 ///
 553 /// The `ActiveBorrows` flow analysis, when inspecting any given
 554 /// statement or terminator, needs to "generate" (i.e. set to 1) all
 555 /// of the bits for the borrows that are activated by that
 556 /// statement/terminator.
 557 ///
 558 /// This struct will seek out all places that are assignment-targets
 559 /// for borrows (gathered in `self.assigned_map`; see also the
 560 /// `assigned_map` in `struct Borrows`), and set the corresponding
 561 /// gen-bits for activations of those borrows in `self.sets`
 562 struct FindPlaceUses<'a, 'b: 'a, 'tcx: 'a> {
 563     assigned_map: &'a FxHashMap<Place<'tcx>, FxHashSet<BorrowIndex>>,
 564     sets: &'a mut BlockSets<'b, ReserveOrActivateIndex>,
 565 }
 566
 567 impl<'a, 'b, 'tcx> FindPlaceUses<'a, 'b, 'tcx> {
 568     fn has_been_reserved(&self, b: &BorrowIndex) -> bool {
 569         self.sets.on_entry.contains(&ReserveOrActivateIndex::reserved(*b))
 570     }
 571
 572     /// return whether `context` should be considered a "use" of a
 573     /// place found in that context. "Uses" activate associated
 574     /// borrows (at least when such uses occur while the borrow also
 575     /// has a reservation at the time).
 576     fn is_potential_use(context: PlaceContext) -> bool {
 577         match context {
 578             // storage effects on a place do not activate it
 579             PlaceContext::StorageLive | PlaceContext::StorageDead => false,
 580
 581             // validation effects do not activate a place
 582             //
 583             // FIXME: Should they? Is it just another read? Or can we
 584             // guarantee it won't dereference the stored address? How
 585             // "deep" does validation go?
 586             PlaceContext::Validate => false,
 587
 588             // FIXME: This is here to not change behaviour from before
 589             // AsmOutput existed, but it's not necessarily a pure overwrite.
 590             // so it's possible this should activate the place.
 591             PlaceContext::AsmOutput |
 592             // pure overwrites of a place do not activate it. (note
 593             // PlaceContext::Call is solely about dest place)
 594             PlaceContext::Store | PlaceContext::Call => false,
 595
 596             // reads of a place *do* activate it
 597             PlaceContext::Move |
 598             PlaceContext::Copy |
 599             PlaceContext::Drop |
 600             PlaceContext::Inspect |
 601             PlaceContext::Borrow { .. } |
 602             PlaceContext::Projection(..) => true,
 603         }
 604     }
 605 }
 606
 607 impl<'a, 'b, 'tcx> Visitor<'tcx> for FindPlaceUses<'a, 'b, 'tcx> {
 608     fn visit_place(&mut self,
 609                     place: &mir::Place<'tcx>,
 610                     context: PlaceContext<'tcx>,
 611                     location: Location) {
 612         debug!("FindPlaceUses place: {:?} assigned from borrows: {:?} \
 613                 used in context: {:?} at location: {:?}",
 614                place, self.assigned_map.get(place), context, location);
 615         if Self::is_potential_use(context) {
 616             if let Some(borrows) = self.assigned_map.get(place) {
 617                 for borrow_idx in borrows {
 618                     debug!("checking if index {:?} for {:?} is reserved ({}) \
 619                             and thus needs active gen-bit set in sets {:?}",
 620                            borrow_idx, place, self.has_been_reserved(&borrow_idx), self.sets);
 621                     if self.has_been_reserved(&borrow_idx) {
 622                         self.sets.gen(&ReserveOrActivateIndex::active(*borrow_idx));
 623                     } else {
 624                         // (This can certainly happen in valid code. I
 625                         // just want to know about it in the short
 626                         // term.)
 627                         debug!("encountered use of Place {:?} of borrow_idx {:?} \
 628                                 at location {:?} outside of reservation",
 629                                place, borrow_idx, location);
 630                     }
 631                 }
 632             }
 633         }
 634
 635         self.super_place(place, context, location);
 636     }
 637 }
 638
 639
 640 impl<'a, 'gcx, 'tcx> BitDenotation for Reservations<'a, 'gcx, 'tcx> {
 641     type Idx = ReserveOrActivateIndex;
 642     fn name() -> &'static str { "reservations" }
 643     fn bits_per_block(&self) -> usize {
 644         self.0.borrows.len() * 2
 645     }
 646     fn start_block_effect(&self, _entry_set: &mut IdxSet<ReserveOrActivateIndex>)  {
 647         // no borrows of code region_scopes have been taken prior to
 648         // function execution, so this method has no effect on
 649         // `_sets`.
 650     }
 651
 652     fn before_statement_effect(&self,
 653                                sets: &mut BlockSets<ReserveOrActivateIndex>,
 654                                location: Location) {
 655         debug!("Reservations::before_statement_effect sets: {:?} location: {:?}", sets, location);
 656         self.0.kill_loans_out_of_scope_at_location(sets, location, false);
 657     }
 658
 659     fn statement_effect(&self,
 660                         sets: &mut BlockSets<ReserveOrActivateIndex>,
 661                         location: Location) {
 662         debug!("Reservations::statement_effect sets: {:?} location: {:?}", sets, location);
 663         self.0.statement_effect_on_borrows(sets, location, false);
 664     }
 665
 666     fn before_terminator_effect(&self,
 667                                 sets: &mut BlockSets<ReserveOrActivateIndex>,
 668                                 location: Location) {
 669         debug!("Reservations::before_terminator_effect sets: {:?} location: {:?}", sets, location);
 670         self.0.kill_loans_out_of_scope_at_location(sets, location, false);
 671     }
 672
 673     fn terminator_effect(&self,
 674                          sets: &mut BlockSets<ReserveOrActivateIndex>,
 675                          location: Location) {
 676         debug!("Reservations::terminator_effect sets: {:?} location: {:?}", sets, location);
 677         self.0.terminator_effect_on_borrows(sets, location, false);
 678     }
 679
 680     fn propagate_call_return(&self,
 681                              _in_out: &mut IdxSet<ReserveOrActivateIndex>,
 682                              _call_bb: mir::BasicBlock,
 683                              _dest_bb: mir::BasicBlock,
 684                              _dest_place: &mir::Place) {
 685         // there are no effects on borrows from method call return...
 686         //
 687         // ... but if overwriting a place can affect flow state, then
 688         // latter is not true; see NOTE on Assign case in
 689         // statement_effect_on_borrows.
 690     }
 691 }
 692
 693 impl<'a, 'gcx, 'tcx> BitDenotation for ActiveBorrows<'a, 'gcx, 'tcx> {
 694     type Idx = ReserveOrActivateIndex;
 695     fn name() -> &'static str { "active_borrows" }
 696
 697     /// Overriding this method; `ActiveBorrows` uses the intrablock
 698     /// state in `on_entry` to track the current reservations (which
 699     /// then affect the construction of the gen/kill sets for
 700     /// activations).
 701     fn accumulates_intrablock_state() -> bool { true }
 702
 703     fn bits_per_block(&self) -> usize {
 704         self.0.borrows.len() * 2
 705     }
 706
 707     fn start_block_effect(&self, _entry_sets: &mut IdxSet<ReserveOrActivateIndex>)  {
 708         // no borrows of code region_scopes have been taken prior to
 709         // function execution, so this method has no effect on
 710         // `_sets`.
 711     }
 712
 713     fn before_statement_effect(&self,
 714                                sets: &mut BlockSets<ReserveOrActivateIndex>,
 715                                location: Location) {
 716         debug!("ActiveBorrows::before_statement_effect sets: {:?} location: {:?}", sets, location);
 717         self.0.kill_loans_out_of_scope_at_location(sets, location, true);
 718     }
 719
 720     fn statement_effect(&self,
 721                         sets: &mut BlockSets<ReserveOrActivateIndex>,
 722                         location: Location) {
 723         debug!("ActiveBorrows::statement_effect sets: {:?} location: {:?}", sets, location);
 724         self.0.statement_effect_on_borrows(sets, location, true);
 725     }
 726
 727     fn before_terminator_effect(&self,
 728                                 sets: &mut BlockSets<ReserveOrActivateIndex>,
 729                                 location: Location) {
 730         debug!("ActiveBorrows::before_terminator_effect sets: {:?} location: {:?}", sets, location);
 731         self.0.kill_loans_out_of_scope_at_location(sets, location, true);
 732     }
 733
 734     fn terminator_effect(&self,
 735                          sets: &mut BlockSets<ReserveOrActivateIndex>,
 736                          location: Location) {
 737         debug!("ActiveBorrows::terminator_effect sets: {:?} location: {:?}", sets, location);
 738         self.0.terminator_effect_on_borrows(sets, location, true);
 739     }
 740
 741     fn propagate_call_return(&self,
 742                              _in_out: &mut IdxSet<ReserveOrActivateIndex>,
 743                              _call_bb: mir::BasicBlock,
 744                              _dest_bb: mir::BasicBlock,
 745                              _dest_place: &mir::Place) {
 746         // there are no effects on borrows from method call return...
 747         //
 748         // ... but If overwriting a place can affect flow state, then
 749         // latter is not true; see NOTE on Assign case in
 750         // statement_effect_on_borrows.
 751     }
 752 }
 753
 754 impl<'a, 'gcx, 'tcx> BitwiseOperator for Reservations<'a, 'gcx, 'tcx> {
 755     #[inline]
 756     fn join(&self, pred1: usize, pred2: usize) -> usize {
 757         pred1 | pred2 // union effects of preds when computing reservations
 758     }
 759 }
 760
 761 impl<'a, 'gcx, 'tcx> BitwiseOperator for ActiveBorrows<'a, 'gcx, 'tcx> {
 762     #[inline]
 763     fn join(&self, pred1: usize, pred2: usize) -> usize {
 764         pred1 | pred2 // union effects of preds when computing activations
 765     }
 766 }
 767
 768 impl<'a, 'gcx, 'tcx> InitialFlow for Reservations<'a, 'gcx, 'tcx> {
 769     #[inline]
 770     fn bottom_value() -> bool {
 771         false // bottom = no Rvalue::Refs are reserved by default
 772     }
 773 }
 774
 775 fn is_unsafe_place<'a, 'gcx: 'tcx, 'tcx: 'a>(
 776     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 777     mir: &'a Mir<'tcx>,
 778     place: &mir::Place<'tcx>
 779 ) -> bool {
 780     use self::mir::Place::*;
 781     use self::mir::ProjectionElem;
 782
 783     match *place {
 784         Local(_) => false,
 785         Static(ref static_) => tcx.is_static_mut(static_.def_id),
 786         Projection(ref proj) => {
 787             match proj.elem {
 788                 ProjectionElem::Field(..) |
 789                 ProjectionElem::Downcast(..) |
 790                 ProjectionElem::Subslice { .. } |
 791                 ProjectionElem::ConstantIndex { .. } |
 792                 ProjectionElem::Index(_) => {
 793                     is_unsafe_place(tcx, mir, &proj.base)
 794                 }
 795                 ProjectionElem::Deref => {
 796                     let ty = proj.base.ty(mir, tcx).to_ty(tcx);
 797                     match ty.sty {
 798                         ty::TyRawPtr(..) => true,
 799                         _ => is_unsafe_place(tcx, mir, &proj.base),
 800                     }
 801                 }
 802             }
 803         }
 804     }
 805 }