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 rustc::mir::{self, Location, Mir};
  12 use rustc::mir::visit::Visitor;
  13 use rustc::ty::{self, Region, TyCtxt};
  14 use rustc::ty::RegionKind;
  15 use rustc::ty::RegionKind::ReScope;
  16 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  17
  18 use rustc_data_structures::bitslice::{BitwiseOperator};
  19 use rustc_data_structures::indexed_set::{IdxSet};
  20 use rustc_data_structures::indexed_vec::{IndexVec};
  21
  22 use dataflow::{BitDenotation, BlockSets, DataflowOperator};
  23 pub use dataflow::indexes::BorrowIndex;
  24 use transform::nll::region_infer::RegionInferenceContext;
  25 use transform::nll::ToRegionVid;
  26
  27 use syntax_pos::Span;
  28
  29 use std::fmt;
  30
  31 // `Borrows` maps each dataflow bit to an `Rvalue::Ref`, which can be
  32 // uniquely identified in the MIR by the `Location` of the assigment
  33 // statement in which it appears on the right hand side.
  34 pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
  35     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  36     mir: &'a Mir<'tcx>,
  37     borrows: IndexVec<BorrowIndex, BorrowData<'tcx>>,
  38     location_map: FxHashMap<Location, BorrowIndex>,
  39     region_map: FxHashMap<Region<'tcx>, FxHashSet<BorrowIndex>>,
  40     region_span_map: FxHashMap<RegionKind, Span>,
  41     nonlexical_regioncx: Option<&'a RegionInferenceContext<'tcx>>,
  42 }
  43
  44 // temporarily allow some dead fields: `kind` and `region` will be
  45 // needed by borrowck; `place` will probably be a MovePathIndex when
  46 // that is extended to include borrowed data paths.
  47 #[allow(dead_code)]
  48 #[derive(Debug)]
  49 pub struct BorrowData<'tcx> {
  50     pub(crate) location: Location,
  51     pub(crate) kind: mir::BorrowKind,
  52     pub(crate) region: Region<'tcx>,
  53     pub(crate) place: mir::Place<'tcx>,
  54 }
  55
  56 impl<'tcx> fmt::Display for BorrowData<'tcx> {
  57     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
  58         let kind = match self.kind {
  59             mir::BorrowKind::Shared => "",
  60             mir::BorrowKind::Unique => "uniq ",
  61             mir::BorrowKind::Mut => "mut ",
  62         };
  63         let region = format!("{}", self.region);
  64         let region = if region.len() > 0 { format!("{} ", region) } else { region };
  65         write!(w, "&{}{}{:?}", region, kind, self.place)
  66     }
  67 }
  68
  69 impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
  70     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
  71                mir: &'a Mir<'tcx>,
  72                nonlexical_regioncx: Option<&'a RegionInferenceContext<'tcx>>)
  73                -> Self {
  74         let mut visitor = GatherBorrows {
  75             tcx,
  76             mir,
  77             idx_vec: IndexVec::new(),
  78             location_map: FxHashMap(),
  79             region_map: FxHashMap(),
  80             region_span_map: FxHashMap()
  81         };
  82         visitor.visit_mir(mir);
  83         return Borrows { tcx: tcx,
  84                          mir: mir,
  85                          borrows: visitor.idx_vec,
  86                          location_map: visitor.location_map,
  87                          region_map: visitor.region_map,
  88                          region_span_map: visitor.region_span_map,
  89                          nonlexical_regioncx };
  90
  91         struct GatherBorrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
  92             tcx: TyCtxt<'a, 'gcx, 'tcx>,
  93             mir: &'a Mir<'tcx>,
  94             idx_vec: IndexVec<BorrowIndex, BorrowData<'tcx>>,
  95             location_map: FxHashMap<Location, BorrowIndex>,
  96             region_map: FxHashMap<Region<'tcx>, FxHashSet<BorrowIndex>>,
  97             region_span_map: FxHashMap<RegionKind, Span>,
  98         }
  99
 100         impl<'a, 'gcx, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'gcx, 'tcx> {
 101             fn visit_rvalue(&mut self,
 102                             rvalue: &mir::Rvalue<'tcx>,
 103                             location: mir::Location) {
 104                 if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue {
 105                     if is_unsafe_place(self.tcx, self.mir, place) { return; }
 106
 107                     let borrow = BorrowData {
 108                         location: location, kind: kind, region: region, place: place.clone(),
 109                     };
 110                     let idx = self.idx_vec.push(borrow);
 111                     self.location_map.insert(location, idx);
 112                     let borrows = self.region_map.entry(region).or_insert(FxHashSet());
 113                     borrows.insert(idx);
 114                 }
 115             }
 116
 117             fn visit_statement(&mut self,
 118                                block: mir::BasicBlock,
 119                                statement: &mir::Statement<'tcx>,
 120                                location: Location) {
 121                 if let mir::StatementKind::EndRegion(region_scope) = statement.kind {
 122                     self.region_span_map.insert(ReScope(region_scope), statement.source_info.span);
 123                 }
 124                 self.super_statement(block, statement, location);
 125             }
 126         }
 127     }
 128
 129     pub fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrows }
 130
 131     pub fn location(&self, idx: BorrowIndex) -> &Location {
 132         &self.borrows[idx].location
 133     }
 134
 135     /// Returns the span for the "end point" given region. This will
 136     /// return `None` if NLL is enabled, since that concept has no
 137     /// meaning there.  Otherwise, return region span if it exists and
 138     /// span for end of the function if it doesn't exist.
 139     pub fn opt_region_end_span(&self, region: &Region) -> Option<Span> {
 140         match self.nonlexical_regioncx {
 141             Some(_) => None,
 142             None => {
 143                 match self.region_span_map.get(region) {
 144                     Some(span) => Some(span.end_point()),
 145                     None => Some(self.mir.span.end_point())
 146                 }
 147             }
 148         }
 149     }
 150
 151     /// Add all borrows to the kill set, if those borrows are out of scope at `location`.
 152     fn kill_loans_out_of_scope_at_location(&self,
 153                                            sets: &mut BlockSets<BorrowIndex>,
 154                                            location: Location) {
 155         if let Some(regioncx) = self.nonlexical_regioncx {
 156             for (borrow_index, borrow_data) in self.borrows.iter_enumerated() {
 157                 let borrow_region = borrow_data.region.to_region_vid();
 158                 if !regioncx.region_contains_point(borrow_region, location) {
 159                     // The region checker really considers the borrow
 160                     // to start at the point **after** the location of
 161                     // the borrow, but the borrow checker puts the gen
 162                     // directly **on** the location of the
 163                     // borrow. This results in a gen/kill both being
 164                     // generated for same point if we are not
 165                     // careful. Probably we should change the point of
 166                     // the gen, but for now we hackily account for the
 167                     // mismatch here by not generating a kill for the
 168                     // location on the borrow itself.
 169                     if location != borrow_data.location {
 170                         sets.kill(&borrow_index);
 171                     }
 172                 }
 173             }
 174         }
 175     }
 176 }
 177
 178 impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
 179     type Idx = BorrowIndex;
 180     fn name() -> &'static str { "borrows" }
 181     fn bits_per_block(&self) -> usize {
 182         self.borrows.len()
 183     }
 184     fn start_block_effect(&self, _sets: &mut BlockSets<BorrowIndex>)  {
 185         // no borrows of code region_scopes have been taken prior to
 186         // function execution, so this method has no effect on
 187         // `_sets`.
 188     }
 189     fn statement_effect(&self,
 190                         sets: &mut BlockSets<BorrowIndex>,
 191                         location: Location) {
 192         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 193             panic!("could not find block at location {:?}", location);
 194         });
 195         let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| {
 196             panic!("could not find statement at location {:?}");
 197         });
 198         match stmt.kind {
 199             mir::StatementKind::EndRegion(region_scope) => {
 200                 if let Some(borrow_indexes) = self.region_map.get(&ReScope(region_scope)) {
 201                     assert!(self.nonlexical_regioncx.is_none());
 202                     for idx in borrow_indexes { sets.kill(&idx); }
 203                 } else {
 204                     // (if there is no entry, then there are no borrows to be tracked)
 205                 }
 206             }
 207
 208             mir::StatementKind::Assign(_, ref rhs) => {
 209                 if let mir::Rvalue::Ref(region, _, ref place) = *rhs {
 210                     if is_unsafe_place(self.tcx, self.mir, place) { return; }
 211                     let index = self.location_map.get(&location).unwrap_or_else(|| {
 212                         panic!("could not find BorrowIndex for location {:?}", location);
 213                     });
 214                     assert!(self.region_map.get(region).unwrap_or_else(|| {
 215                         panic!("could not find BorrowIndexs for region {:?}", region);
 216                     }).contains(&index));
 217                     sets.gen(&index);
 218                 }
 219             }
 220
 221             mir::StatementKind::InlineAsm { .. } |
 222             mir::StatementKind::SetDiscriminant { .. } |
 223             mir::StatementKind::StorageLive(..) |
 224             mir::StatementKind::StorageDead(..) |
 225             mir::StatementKind::Validate(..) |
 226             mir::StatementKind::Nop => {}
 227
 228         }
 229
 230         self.kill_loans_out_of_scope_at_location(sets, location);
 231     }
 232
 233     fn terminator_effect(&self,
 234                          sets: &mut BlockSets<BorrowIndex>,
 235                          location: Location) {
 236         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 237             panic!("could not find block at location {:?}", location);
 238         });
 239         match block.terminator().kind {
 240             mir::TerminatorKind::Resume |
 241             mir::TerminatorKind::Return |
 242             mir::TerminatorKind::GeneratorDrop => {
 243                 // When we return from the function, then all `ReScope`-style regions
 244                 // are guaranteed to have ended.
 245                 // Normally, there would be `EndRegion` statements that come before,
 246                 // and hence most of these loans will already be dead -- but, in some cases
 247                 // like unwind paths, we do not always emit `EndRegion` statements, so we
 248                 // add some kills here as a "backup" and to avoid spurious error messages.
 249                 for (borrow_index, borrow_data) in self.borrows.iter_enumerated() {
 250                     if let ReScope(..) = borrow_data.region {
 251                         sets.kill(&borrow_index);
 252                     }
 253                 }
 254             }
 255             mir::TerminatorKind::SwitchInt {..} |
 256             mir::TerminatorKind::Drop {..} |
 257             mir::TerminatorKind::DropAndReplace {..} |
 258             mir::TerminatorKind::Call {..} |
 259             mir::TerminatorKind::Assert {..} |
 260             mir::TerminatorKind::Yield {..} |
 261             mir::TerminatorKind::Goto {..} |
 262             mir::TerminatorKind::FalseEdges {..} |
 263             mir::TerminatorKind::Unreachable => {}
 264         }
 265         self.kill_loans_out_of_scope_at_location(sets, location);
 266     }
 267
 268     fn propagate_call_return(&self,
 269                              _in_out: &mut IdxSet<BorrowIndex>,
 270                              _call_bb: mir::BasicBlock,
 271                              _dest_bb: mir::BasicBlock,
 272                              _dest_place: &mir::Place) {
 273         // there are no effects on the region scopes from method calls.
 274     }
 275 }
 276
 277 impl<'a, 'gcx, 'tcx> BitwiseOperator for Borrows<'a, 'gcx, 'tcx> {
 278     #[inline]
 279     fn join(&self, pred1: usize, pred2: usize) -> usize {
 280         pred1 | pred2 // union effects of preds when computing borrows
 281     }
 282 }
 283
 284 impl<'a, 'gcx, 'tcx> DataflowOperator for Borrows<'a, 'gcx, 'tcx> {
 285     #[inline]
 286     fn bottom_value() -> bool {
 287         false // bottom = no Rvalue::Refs are active by default
 288     }
 289 }
 290
 291 fn is_unsafe_place<'a, 'gcx: 'tcx, 'tcx: 'a>(
 292     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 293     mir: &'a Mir<'tcx>,
 294     place: &mir::Place<'tcx>
 295 ) -> bool {
 296     use self::mir::Place::*;
 297     use self::mir::ProjectionElem;
 298
 299     match *place {
 300         Local(_) => false,
 301         Static(ref static_) => tcx.is_static_mut(static_.def_id),
 302         Projection(ref proj) => {
 303             match proj.elem {
 304                 ProjectionElem::Field(..) |
 305                 ProjectionElem::Downcast(..) |
 306                 ProjectionElem::Subslice { .. } |
 307                 ProjectionElem::ConstantIndex { .. } |
 308                 ProjectionElem::Index(_) => {
 309                     is_unsafe_place(tcx, mir, &proj.base)
 310                 }
 311                 ProjectionElem::Deref => {
 312                     let ty = proj.base.ty(mir, tcx).to_ty(tcx);
 313                     match ty.sty {
 314                         ty::TyRawPtr(..) => true,
 315                         _ => is_unsafe_place(tcx, mir, &proj.base),
 316                     }
 317                 }
 318             }
 319         }
 320     }
 321 }