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