compiler/rustc_borrowck/src/borrow_set.rs

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