src/librustc_mir/borrow_check/borrow_set.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 borrow_check::place_ext::PlaceExt;
  12 use dataflow::indexes::BorrowIndex;
  13 use dataflow::move_paths::MoveData;
  14 use rustc::mir::traversal;
  15 use rustc::mir::visit::{PlaceContext, Visitor};
  16 use rustc::mir::{self, Location, Mir, Place, Local};
  17 use rustc::ty::{Region, TyCtxt};
  18 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  19 use rustc_data_structures::indexed_vec::IndexVec;
  20 use rustc_data_structures::bit_set::BitSet;
  21 use std::fmt;
  22 use std::hash::Hash;
  23 use std::ops::Index;
  24
  25 crate struct BorrowSet<'tcx> {
  26     /// The fundamental map relating bitvector indexes to the borrows
  27     /// in the MIR.
  28     crate borrows: IndexVec<BorrowIndex, BorrowData<'tcx>>,
  29
  30     /// Each borrow is also uniquely identified in the MIR by the
  31     /// `Location` of the assignment statement in which it appears on
  32     /// the right hand side; we map each such location to the
  33     /// corresponding `BorrowIndex`.
  34     crate location_map: FxHashMap<Location, BorrowIndex>,
  35
  36     /// Locations which activate borrows.
  37     /// NOTE: A given location may activate more than one borrow in the future
  38     /// when more general two-phase borrow support is introduced, but for now we
  39     /// only need to store one borrow index
  40     crate activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
  41
  42     /// Every borrow has a region; this maps each such regions back to
  43     /// its borrow-indexes.
  44     crate region_map: FxHashMap<Region<'tcx>, FxHashSet<BorrowIndex>>,
  45
  46     /// Map from local to all the borrows on that local
  47     crate local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
  48
  49     crate locals_state_at_exit: LocalsStateAtExit,
  50 }
  51
  52 impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> {
  53     type Output = BorrowData<'tcx>;
  54
  55     fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> {
  56         &self.borrows[index]
  57     }
  58 }
  59
  60 /// Location where a two phase borrow is activated, if a borrow
  61 /// is in fact a two phase borrow.
  62 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  63 crate enum TwoPhaseActivation {
  64     NotTwoPhase,
  65     NotActivated,
  66     ActivatedAt(Location),
  67 }
  68
  69 #[derive(Debug)]
  70 crate struct BorrowData<'tcx> {
  71     /// Location where the borrow reservation starts.
  72     /// In many cases, this will be equal to the activation location but not always.
  73     crate reserve_location: Location,
  74     /// Location where the borrow is activated.
  75     crate activation_location: TwoPhaseActivation,
  76     /// What kind of borrow this is
  77     crate kind: mir::BorrowKind,
  78     /// The region for which this borrow is live
  79     crate region: Region<'tcx>,
  80     /// Place from which we are borrowing
  81     crate borrowed_place: mir::Place<'tcx>,
  82     /// Place to which the borrow was stored
  83     crate assigned_place: mir::Place<'tcx>,
  84 }
  85
  86 impl<'tcx> fmt::Display for BorrowData<'tcx> {
  87     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
  88         let kind = match self.kind {
  89             mir::BorrowKind::Shared => "",
  90             mir::BorrowKind::Shallow => "shallow ",
  91             mir::BorrowKind::Unique => "uniq ",
  92             mir::BorrowKind::Mut { .. } => "mut ",
  93         };
  94         let region = self.region.to_string();
  95         let region = if region.len() > 0 {
  96             format!("{} ", region)
  97         } else {
  98             region
  99         };
 100         write!(w, "&{}{}{:?}", region, kind, self.borrowed_place)
 101     }
 102 }
 103
 104 crate enum LocalsStateAtExit {
 105     AllAreInvalidated,
 106     SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }
 107 }
 108
 109 impl LocalsStateAtExit {
 110     fn build(
 111         locals_are_invalidated_at_exit: bool,
 112         mir: &Mir<'tcx>,
 113         move_data: &MoveData<'tcx>
 114     ) -> Self {
 115         struct HasStorageDead(BitSet<Local>);
 116
 117         impl<'tcx> Visitor<'tcx> for HasStorageDead {
 118             fn visit_local(&mut self, local: &Local, ctx: PlaceContext<'tcx>, _: Location) {
 119                 if ctx == PlaceContext::StorageDead {
 120                     self.0.insert(*local);
 121                 }
 122             }
 123         }
 124
 125         if locals_are_invalidated_at_exit {
 126             LocalsStateAtExit::AllAreInvalidated
 127         } else {
 128             let mut has_storage_dead = HasStorageDead(BitSet::new_empty(mir.local_decls.len()));
 129             has_storage_dead.visit_mir(mir);
 130             let mut has_storage_dead_or_moved = has_storage_dead.0;
 131             for move_out in &move_data.moves {
 132                 if let Some(index) = move_data.base_local(move_out.path) {
 133                     has_storage_dead_or_moved.insert(index);
 134
 135                 }
 136             }
 137             LocalsStateAtExit::SomeAreInvalidated{ has_storage_dead_or_moved }
 138         }
 139     }
 140 }
 141
 142 impl<'tcx> BorrowSet<'tcx> {
 143     pub fn build(
 144         tcx: TyCtxt<'_, '_, 'tcx>,
 145         mir: &Mir<'tcx>,
 146         locals_are_invalidated_at_exit: bool,
 147         move_data: &MoveData<'tcx>
 148     ) -> Self {
 149
 150         let mut visitor = GatherBorrows {
 151             tcx,
 152             mir,
 153             idx_vec: IndexVec::new(),
 154             location_map: FxHashMap(),
 155             activation_map: FxHashMap(),
 156             region_map: FxHashMap(),
 157             local_map: FxHashMap(),
 158             pending_activations: FxHashMap(),
 159             locals_state_at_exit:
 160                 LocalsStateAtExit::build(locals_are_invalidated_at_exit, mir, move_data),
 161         };
 162
 163         for (block, block_data) in traversal::preorder(mir) {
 164             visitor.visit_basic_block_data(block, block_data);
 165         }
 166
 167         BorrowSet {
 168             borrows: visitor.idx_vec,
 169             location_map: visitor.location_map,
 170             activation_map: visitor.activation_map,
 171             region_map: visitor.region_map,
 172             local_map: visitor.local_map,
 173             locals_state_at_exit: visitor.locals_state_at_exit,
 174         }
 175     }
 176
 177     crate fn activations_at_location(&self, location: Location) -> &[BorrowIndex] {
 178         self.activation_map
 179             .get(&location)
 180             .map(|activations| &activations[..])
 181             .unwrap_or(&[])
 182     }
 183 }
 184
 185 struct GatherBorrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
 186     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 187     mir: &'a Mir<'tcx>,
 188     idx_vec: IndexVec<BorrowIndex, BorrowData<'tcx>>,
 189     location_map: FxHashMap<Location, BorrowIndex>,
 190     activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
 191     region_map: FxHashMap<Region<'tcx>, FxHashSet<BorrowIndex>>,
 192     local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
 193
 194     /// When we encounter a 2-phase borrow statement, it will always
 195     /// be assigning into a temporary TEMP:
 196     ///
 197     ///    TEMP = &foo
 198     ///
 199     /// We add TEMP into this map with `b`, where `b` is the index of
 200     /// the borrow. When we find a later use of this activation, we
 201     /// remove from the map (and add to the "tombstone" set below).
 202     pending_activations: FxHashMap<mir::Local, BorrowIndex>,
 203
 204     locals_state_at_exit: LocalsStateAtExit,
 205 }
 206
 207 impl<'a, 'gcx, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'gcx, 'tcx> {
 208     fn visit_assign(
 209         &mut self,
 210         block: mir::BasicBlock,
 211         assigned_place: &mir::Place<'tcx>,
 212         rvalue: &mir::Rvalue<'tcx>,
 213         location: mir::Location,
 214     ) {
 215         if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue {
 216             if borrowed_place.ignore_borrow(
 217                 self.tcx, self.mir, &self.locals_state_at_exit) {
 218                 return;
 219             }
 220
 221             let borrow = BorrowData {
 222                 kind,
 223                 region,
 224                 reserve_location: location,
 225                 activation_location: TwoPhaseActivation::NotTwoPhase,
 226                 borrowed_place: borrowed_place.clone(),
 227                 assigned_place: assigned_place.clone(),
 228             };
 229             let idx = self.idx_vec.push(borrow);
 230             self.location_map.insert(location, idx);
 231
 232             self.insert_as_pending_if_two_phase(location, &assigned_place, region, kind, idx);
 233
 234             insert(&mut self.region_map, &region, idx);
 235             if let Some(local) = borrowed_place.root_local() {
 236                 insert(&mut self.local_map, &local, idx);
 237             }
 238         }
 239
 240         return self.super_assign(block, assigned_place, rvalue, location);
 241
 242         fn insert<'a, K, V>(map: &'a mut FxHashMap<K, FxHashSet<V>>, k: &K, v: V)
 243         where
 244             K: Clone + Eq + Hash,
 245             V: Eq + Hash,
 246         {
 247             map.entry(k.clone()).or_insert(FxHashSet()).insert(v);
 248         }
 249     }
 250
 251     fn visit_place(
 252         &mut self,
 253         place: &mir::Place<'tcx>,
 254         context: PlaceContext<'tcx>,
 255         location: Location,
 256     ) {
 257         self.super_place(place, context, location);
 258
 259         // We found a use of some temporary TEMP...
 260         if let Place::Local(temp) = place {
 261             // ... check whether we (earlier) saw a 2-phase borrow like
 262             //
 263             //     TMP = &mut place
 264             match self.pending_activations.get(temp) {
 265                 Some(&borrow_index) => {
 266                     let borrow_data = &mut self.idx_vec[borrow_index];
 267
 268                     // Watch out: the use of TMP in the borrow itself
 269                     // doesn't count as an activation. =)
 270                     if borrow_data.reserve_location == location && context == PlaceContext::Store {
 271                         return;
 272                     }
 273
 274                     if let TwoPhaseActivation::ActivatedAt(other_location) =
 275                             borrow_data.activation_location {
 276                         span_bug!(
 277                             self.mir.source_info(location).span,
 278                             "found two uses for 2-phase borrow temporary {:?}: \
 279                              {:?} and {:?}",
 280                             temp,
 281                             location,
 282                             other_location,
 283                         );
 284                     }
 285
 286                     // Otherwise, this is the unique later use
 287                     // that we expect.
 288                     borrow_data.activation_location = match context {
 289                         // The use of TMP in a shared borrow does not
 290                         // count as an actual activation.
 291                         PlaceContext::Borrow { kind: mir::BorrowKind::Shared, .. }
 292                         | PlaceContext::Borrow { kind: mir::BorrowKind::Shallow, .. } => {
 293                             TwoPhaseActivation::NotActivated
 294                         }
 295                         _ => {
 296                             // Double check: This borrow is indeed a two-phase borrow (that is,
 297                             // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and
 298                             // we've not found any other activations (checked above).
 299                             assert_eq!(
 300                                 borrow_data.activation_location,
 301                                 TwoPhaseActivation::NotActivated,
 302                                 "never found an activation for this borrow!",
 303                             );
 304
 305                             self.activation_map
 306                                 .entry(location)
 307                                 .or_default()
 308                                 .push(borrow_index);
 309                             TwoPhaseActivation::ActivatedAt(location)
 310                         }
 311                     };
 312                 }
 313
 314                 None => {}
 315             }
 316         }
 317     }
 318
 319     fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location) {
 320         if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue {
 321             // double-check that we already registered a BorrowData for this
 322
 323             let borrow_index = self.location_map[&location];
 324             let borrow_data = &self.idx_vec[borrow_index];
 325             assert_eq!(borrow_data.reserve_location, location);
 326             assert_eq!(borrow_data.kind, kind);
 327             assert_eq!(borrow_data.region, region);
 328             assert_eq!(borrow_data.borrowed_place, *place);
 329         }
 330
 331         return self.super_rvalue(rvalue, location);
 332     }
 333
 334     fn visit_statement(
 335         &mut self,
 336         block: mir::BasicBlock,
 337         statement: &mir::Statement<'tcx>,
 338         location: Location,
 339     ) {
 340         return self.super_statement(block, statement, location);
 341     }
 342 }
 343
 344 impl<'a, 'gcx, 'tcx> GatherBorrows<'a, 'gcx, 'tcx> {
 345     /// Returns true if the borrow represented by `kind` is
 346     /// allowed to be split into separate Reservation and
 347     /// Activation phases.
 348     fn allow_two_phase_borrow(&self, kind: mir::BorrowKind) -> bool {
 349         self.tcx.two_phase_borrows()
 350             && (kind.allows_two_phase_borrow()
 351                 || self.tcx.sess.opts.debugging_opts.two_phase_beyond_autoref)
 352     }
 353
 354     /// If this is a two-phase borrow, then we will record it
 355     /// as "pending" until we find the activating use.
 356     fn insert_as_pending_if_two_phase(
 357         &mut self,
 358         start_location: Location,
 359         assigned_place: &mir::Place<'tcx>,
 360         region: Region<'tcx>,
 361         kind: mir::BorrowKind,
 362         borrow_index: BorrowIndex,
 363     ) {
 364         debug!(
 365             "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?}, {:?})",
 366             start_location, assigned_place, region, borrow_index,
 367         );
 368
 369         if !self.allow_two_phase_borrow(kind) {
 370             debug!("  -> {:?}", start_location);
 371             return;
 372         }
 373
 374         // When we encounter a 2-phase borrow statement, it will always
 375         // be assigning into a temporary TEMP:
 376         //
 377         //    TEMP = &foo
 378         //
 379         // so extract `temp`.
 380         let temp = if let &mir::Place::Local(temp) = assigned_place {
 381             temp
 382         } else {
 383             span_bug!(
 384                 self.mir.source_info(start_location).span,
 385                 "expected 2-phase borrow to assign to a local, not `{:?}`",
 386                 assigned_place,
 387             );
 388         };
 389
 390         // Consider the borrow not activated to start. When we find an activation, we'll update
 391         // this field.
 392         {
 393             let borrow_data = &mut self.idx_vec[borrow_index];
 394             borrow_data.activation_location = TwoPhaseActivation::NotActivated;
 395         }
 396
 397         // Insert `temp` into the list of pending activations. From
 398         // now on, we'll be on the lookout for a use of it. Note that
 399         // we are guaranteed that this use will come after the
 400         // assignment.
 401         let old_value = self.pending_activations.insert(temp, borrow_index);
 402         if let Some(old_index) = old_value {
 403             span_bug!(self.mir.source_info(start_location).span,
 404                       "found already pending activation for temp: {:?} \
 405                        at borrow_index: {:?} with associated data {:?}",
 406                       temp, old_index, self.idx_vec[old_index]);
 407         }
 408     }
 409 }