compiler/rustc_mir/src/borrow_check/borrow_set.rs

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