src/librustc_mir/borrow_check/borrow_set.rs

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