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