src/librustc_mir/borrow_check/borrow_set.rs

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