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