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