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