src/librustc_mir/dataflow/impls/borrows.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::borrow_set::{BorrowSet, BorrowData};
  12 use borrow_check::place_ext::PlaceExt;
  13
  14 use rustc;
  15 use rustc::hir;
  16 use rustc::hir::def_id::DefId;
  17 use rustc::middle::region;
  18 use rustc::mir::{self, Location, Place, Mir};
  19 use rustc::ty::TyCtxt;
  20 use rustc::ty::{RegionKind, RegionVid};
  21 use rustc::ty::RegionKind::ReScope;
  22
  23 use rustc_data_structures::bitslice::{BitwiseOperator, Word};
  24 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  25 use rustc_data_structures::indexed_set::IdxSet;
  26 use rustc_data_structures::indexed_vec::IndexVec;
  27 use rustc_data_structures::sync::Lrc;
  28
  29 use dataflow::{BitDenotation, BlockSets, InitialFlow};
  30 pub use dataflow::indexes::BorrowIndex;
  31 use borrow_check::nll::region_infer::RegionInferenceContext;
  32 use borrow_check::nll::ToRegionVid;
  33
  34 use std::rc::Rc;
  35
  36 /// `Borrows` stores the data used in the analyses that track the flow
  37 /// of borrows.
  38 ///
  39 /// It uniquely identifies every borrow (`Rvalue::Ref`) by a
  40 /// `BorrowIndex`, and maps each such index to a `BorrowData`
  41 /// describing the borrow. These indexes are used for representing the
  42 /// borrows in compact bitvectors.
  43 pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
  44     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  45     mir: &'a Mir<'tcx>,
  46     scope_tree: Lrc<region::ScopeTree>,
  47     root_scope: Option<region::Scope>,
  48
  49     borrow_set: Rc<BorrowSet<'tcx>>,
  50     borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>,
  51
  52     /// NLL region inference context with which NLL queries should be resolved
  53     _nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
  54 }
  55
  56 fn precompute_borrows_out_of_scope<'tcx>(
  57     mir: &Mir<'tcx>,
  58     regioncx: &Rc<RegionInferenceContext<'tcx>>,
  59     borrows_out_of_scope_at_location: &mut FxHashMap<Location, Vec<BorrowIndex>>,
  60     borrow_index: BorrowIndex,
  61     borrow_region: RegionVid,
  62     location: Location,
  63 ) {
  64     // Keep track of places we've locations to check and locations that we have checked.
  65     let mut stack = vec![ location ];
  66     let mut visited = FxHashSet();
  67     visited.insert(location);
  68
  69     debug!(
  70         "borrow {:?} has region {:?} with value {:?}",
  71         borrow_index,
  72         borrow_region,
  73         regioncx.region_value_str(borrow_region),
  74     );
  75     debug!("borrow {:?} starts at {:?}", borrow_index, location);
  76     while let Some(location) = stack.pop() {
  77         // If region does not contain a point at the location, then add to list and skip
  78         // successor locations.
  79         if !regioncx.region_contains(borrow_region, location) {
  80             debug!("borrow {:?} gets killed at {:?}", borrow_index, location);
  81             borrows_out_of_scope_at_location
  82                 .entry(location)
  83                 .or_insert(vec![])
  84                 .push(borrow_index);
  85             continue;
  86         }
  87
  88         let bb_data = &mir[location.block];
  89         // If this is the last statement in the block, then add the
  90         // terminator successors next.
  91         if location.statement_index == bb_data.statements.len() {
  92             // Add successors to locations to visit, if not visited before.
  93             if let Some(ref terminator) = bb_data.terminator {
  94                 for block in terminator.successors() {
  95                     let loc = block.start_location();
  96                     if visited.insert(loc) {
  97                         stack.push(loc);
  98                     }
  99                 }
 100             }
 101         } else {
 102             // Visit next statement in block.
 103             let loc = location.successor_within_block();
 104             if visited.insert(loc) {
 105                 stack.push(loc);
 106             }
 107         }
 108     }
 109 }
 110
 111 impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
 112     crate fn new(
 113         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 114         mir: &'a Mir<'tcx>,
 115         nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
 116         def_id: DefId,
 117         body_id: Option<hir::BodyId>,
 118         borrow_set: &Rc<BorrowSet<'tcx>>
 119     ) -> Self {
 120         let scope_tree = tcx.region_scope_tree(def_id);
 121         let root_scope = body_id.map(|body_id| {
 122             region::Scope::CallSite(tcx.hir.body(body_id).value.hir_id.local_id)
 123         });
 124
 125         let mut borrows_out_of_scope_at_location = FxHashMap();
 126         for (borrow_index, borrow_data) in borrow_set.borrows.iter_enumerated() {
 127             let borrow_region = borrow_data.region.to_region_vid();
 128             let location = borrow_set.borrows[borrow_index].reserve_location;
 129
 130             precompute_borrows_out_of_scope(mir, &nonlexical_regioncx,
 131                                             &mut borrows_out_of_scope_at_location,
 132                                             borrow_index, borrow_region, location);
 133         }
 134
 135         Borrows {
 136             tcx: tcx,
 137             mir: mir,
 138             borrow_set: borrow_set.clone(),
 139             borrows_out_of_scope_at_location,
 140             scope_tree,
 141             root_scope,
 142             _nonlexical_regioncx: nonlexical_regioncx,
 143         }
 144     }
 145
 146     crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrow_set.borrows }
 147     pub fn scope_tree(&self) -> &Lrc<region::ScopeTree> { &self.scope_tree }
 148
 149     pub fn location(&self, idx: BorrowIndex) -> &Location {
 150         &self.borrow_set.borrows[idx].reserve_location
 151     }
 152
 153     /// Add all borrows to the kill set, if those borrows are out of scope at `location`.
 154     /// That means either they went out of either a nonlexical scope, if we care about those
 155     /// at the moment, or the location represents a lexical EndRegion
 156     fn kill_loans_out_of_scope_at_location(&self,
 157                                            sets: &mut BlockSets<BorrowIndex>,
 158                                            location: Location) {
 159         // NOTE: The state associated with a given `location`
 160         // reflects the dataflow on entry to the statement.
 161         // Iterate over each of the borrows that we've precomputed
 162         // to have went out of scope at this location and kill them.
 163         //
 164         // We are careful always to call this function *before* we
 165         // set up the gen-bits for the statement or
 166         // termanator. That way, if the effect of the statement or
 167         // terminator *does* introduce a new loan of the same
 168         // region, then setting that gen-bit will override any
 169         // potential kill introduced here.
 170         if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) {
 171             for index in indices {
 172                 sets.kill(&index);
 173             }
 174         }
 175     }
 176
 177     fn kill_borrows_on_local(&self,
 178                              sets: &mut BlockSets<BorrowIndex>,
 179                              local: &rustc::mir::Local)
 180     {
 181         if let Some(borrow_indexes) = self.borrow_set.local_map.get(local) {
 182             sets.kill_all(borrow_indexes);
 183         }
 184     }
 185 }
 186
 187 impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
 188     type Idx = BorrowIndex;
 189     fn name() -> &'static str { "borrows" }
 190     fn bits_per_block(&self) -> usize {
 191         self.borrow_set.borrows.len() * 2
 192     }
 193
 194     fn start_block_effect(&self, _entry_set: &mut IdxSet<BorrowIndex>) {
 195         // no borrows of code region_scopes have been taken prior to
 196         // function execution, so this method has no effect on
 197         // `_sets`.
 198     }
 199
 200     fn before_statement_effect(&self,
 201                                sets: &mut BlockSets<BorrowIndex>,
 202                                location: Location) {
 203         debug!("Borrows::before_statement_effect sets: {:?} location: {:?}", sets, location);
 204         self.kill_loans_out_of_scope_at_location(sets, location);
 205     }
 206
 207     fn statement_effect(&self, sets: &mut BlockSets<BorrowIndex>, location: Location) {
 208         debug!("Borrows::statement_effect sets: {:?} location: {:?}", sets, location);
 209
 210         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 211             panic!("could not find block at location {:?}", location);
 212         });
 213         let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| {
 214             panic!("could not find statement at location {:?}");
 215         });
 216
 217         match stmt.kind {
 218             mir::StatementKind::EndRegion(_) => {
 219             }
 220
 221             mir::StatementKind::Assign(ref lhs, ref rhs) => {
 222                 // Make sure there are no remaining borrows for variables
 223                 // that are assigned over.
 224                 if let Place::Local(ref local) = *lhs {
 225                     // FIXME: Handle the case in which we're assigning over
 226                     // a projection (`foo.bar`).
 227                     self.kill_borrows_on_local(sets, local);
 228                 }
 229
 230                 // NOTE: if/when the Assign case is revised to inspect
 231                 // the assigned_place here, make sure to also
 232                 // re-consider the current implementations of the
 233                 // propagate_call_return method.
 234
 235                 if let mir::Rvalue::Ref(region, _, ref place) = *rhs {
 236                     if place.ignore_borrow(self.tcx, self.mir) { return; }
 237                     let index = self.borrow_set.location_map.get(&location).unwrap_or_else(|| {
 238                         panic!("could not find BorrowIndex for location {:?}", location);
 239                     });
 240
 241                     if let RegionKind::ReEmpty = region {
 242                         // If the borrowed value dies before the borrow is used, the region for
 243                         // the borrow can be empty. Don't track the borrow in that case.
 244                         debug!("Borrows::statement_effect_on_borrows \
 245                                 location: {:?} stmt: {:?} has empty region, killing {:?}",
 246                                location, stmt.kind, index);
 247                         sets.kill(&index);
 248                         return
 249                     } else {
 250                         debug!("Borrows::statement_effect_on_borrows location: {:?} stmt: {:?}",
 251                                location, stmt.kind);
 252                     }
 253
 254                     assert!(self.borrow_set.region_map.get(region).unwrap_or_else(|| {
 255                         panic!("could not find BorrowIndexs for region {:?}", region);
 256                     }).contains(&index));
 257                     sets.gen(&index);
 258
 259                     // Issue #46746: Two-phase borrows handles
 260                     // stmts of form `Tmp = &mut Borrow` ...
 261                     match lhs {
 262                         Place::Promoted(_) |
 263                         Place::Local(..) | Place::Static(..) => {} // okay
 264                         Place::Projection(..) => {
 265                             // ... can assign into projections,
 266                             // e.g. `box (&mut _)`. Current
 267                             // conservative solution: force
 268                             // immediate activation here.
 269                             sets.gen(&index);
 270                         }
 271                     }
 272                 }
 273             }
 274
 275             mir::StatementKind::StorageDead(local) => {
 276                 // Make sure there are no remaining borrows for locals that
 277                 // are gone out of scope.
 278                 self.kill_borrows_on_local(sets, &local)
 279             }
 280
 281             mir::StatementKind::InlineAsm { ref outputs, ref asm, .. } => {
 282                 for (output, kind) in outputs.iter().zip(&asm.outputs) {
 283                     if !kind.is_indirect && !kind.is_rw {
 284                         // Make sure there are no remaining borrows for direct
 285                         // output variables.
 286                         if let Place::Local(ref local) = *output {
 287                             // FIXME: Handle the case in which we're assigning over
 288                             // a projection (`foo.bar`).
 289                             self.kill_borrows_on_local(sets, local);
 290                         }
 291                     }
 292                 }
 293             }
 294
 295             mir::StatementKind::ReadForMatch(..) |
 296             mir::StatementKind::SetDiscriminant { .. } |
 297             mir::StatementKind::StorageLive(..) |
 298             mir::StatementKind::Validate(..) |
 299             mir::StatementKind::UserAssertTy(..) |
 300             mir::StatementKind::Nop => {}
 301
 302         }
 303     }
 304
 305     fn before_terminator_effect(&self,
 306                                 sets: &mut BlockSets<BorrowIndex>,
 307                                 location: Location) {
 308         debug!("Borrows::before_terminator_effect sets: {:?} location: {:?}", sets, location);
 309         self.kill_loans_out_of_scope_at_location(sets, location);
 310     }
 311
 312     fn terminator_effect(&self, sets: &mut BlockSets<BorrowIndex>, location: Location) {
 313         debug!("Borrows::terminator_effect sets: {:?} location: {:?}", sets, location);
 314
 315         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 316             panic!("could not find block at location {:?}", location);
 317         });
 318
 319         let term = block.terminator();
 320         match term.kind {
 321             mir::TerminatorKind::Resume |
 322             mir::TerminatorKind::Return |
 323             mir::TerminatorKind::GeneratorDrop => {
 324                 // When we return from the function, then all `ReScope`-style regions
 325                 // are guaranteed to have ended.
 326                 // Normally, there would be `EndRegion` statements that come before,
 327                 // and hence most of these loans will already be dead -- but, in some cases
 328                 // like unwind paths, we do not always emit `EndRegion` statements, so we
 329                 // add some kills here as a "backup" and to avoid spurious error messages.
 330                 for (borrow_index, borrow_data) in self.borrow_set.borrows.iter_enumerated() {
 331                     if let ReScope(scope) = borrow_data.region {
 332                         // Check that the scope is not actually a scope from a function that is
 333                         // a parent of our closure. Note that the CallSite scope itself is
 334                         // *outside* of the closure, for some weird reason.
 335                         if let Some(root_scope) = self.root_scope {
 336                             if *scope != root_scope &&
 337                                 self.scope_tree.is_subscope_of(*scope, root_scope)
 338                             {
 339                                 sets.kill(&borrow_index);
 340                             }
 341                         }
 342                     }
 343                 }
 344             }
 345             mir::TerminatorKind::Abort |
 346             mir::TerminatorKind::SwitchInt {..} |
 347             mir::TerminatorKind::Drop {..} |
 348             mir::TerminatorKind::DropAndReplace {..} |
 349             mir::TerminatorKind::Call {..} |
 350             mir::TerminatorKind::Assert {..} |
 351             mir::TerminatorKind::Yield {..} |
 352             mir::TerminatorKind::Goto {..} |
 353             mir::TerminatorKind::FalseEdges {..} |
 354             mir::TerminatorKind::FalseUnwind {..} |
 355             mir::TerminatorKind::Unreachable => {}
 356         }
 357     }
 358
 359     fn propagate_call_return(&self,
 360                              _in_out: &mut IdxSet<BorrowIndex>,
 361                              _call_bb: mir::BasicBlock,
 362                              _dest_bb: mir::BasicBlock,
 363                              _dest_place: &mir::Place) {
 364         // there are no effects on borrows from method call return...
 365         //
 366         // ... but if overwriting a place can affect flow state, then
 367         // latter is not true; see NOTE on Assign case in
 368         // statement_effect_on_borrows.
 369     }
 370 }
 371
 372 impl<'a, 'gcx, 'tcx> BitwiseOperator for Borrows<'a, 'gcx, 'tcx> {
 373     #[inline]
 374     fn join(&self, pred1: Word, pred2: Word) -> Word {
 375         pred1 | pred2 // union effects of preds when computing reservations
 376     }
 377 }
 378
 379 impl<'a, 'gcx, 'tcx> InitialFlow for Borrows<'a, 'gcx, 'tcx> {
 380     #[inline]
 381     fn bottom_value() -> bool {
 382         false // bottom = nothing is reserved or activated yet
 383     }
 384 }
 385