src/librustc_mir/borrow_check/borrow_set.rs

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