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