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