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.
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.
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}
;
18 use rustc_data_structures
::bitslice
::{BitwiseOperator}
;
19 use rustc_data_structures
::indexed_set
::{IdxSet}
;
20 use rustc_data_structures
::indexed_vec
::{IndexVec}
;
22 use dataflow
::{BitDenotation, BlockSets, DataflowOperator}
;
23 pub use dataflow
::indexes
::BorrowIndex
;
24 use transform
::nll
::region_infer
::RegionInferenceContext
;
25 use transform
::nll
::ToRegionVid
;
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
>,
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
>>,
44 // temporarily allow some dead fields: `kind` and `region` will be
45 // needed by borrowck; `lvalue` will probably be a MovePathIndex when
46 // that is extended to include borrowed data paths.
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) lvalue
: mir
::Lvalue
<'tcx
>,
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 ",
63 let region
= format
!("{}", self.region
);
64 let region
= if region
.len() > 0 { format!("{}
", region) } else { region };
65 write!(w, "&{}{}{:?}
", region, kind, self.lvalue)
69 impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
70 pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
72 nonlexical_regioncx: Option<&'a RegionInferenceContext<'tcx>>)
74 let mut visitor = GatherBorrows {
77 idx_vec: IndexVec::new(),
78 location_map: FxHashMap(),
79 region_map: FxHashMap(),
80 region_span_map: FxHashMap()
82 visitor.visit_mir(mir);
83 return Borrows { tcx: tcx,
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 };
91 struct GatherBorrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
92 tcx: TyCtxt<'a, 'gcx, '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>,
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 lvalue) = *rvalue {
105 if is_unsafe_lvalue(self.tcx, self.mir, lvalue) { return; }
107 let borrow = BorrowData {
108 location: location, kind: kind, region: region, lvalue: lvalue.clone(),
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());
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);
124 self.super_statement(block, statement, location);
129 pub fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrows }
131 pub fn location(&self, idx: BorrowIndex) -> &Location {
132 &self.borrows[idx].location
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 {
143 match self.region_span_map.get(region) {
144 Some(span) => Some(span.end_point()),
145 None => Some(self.mir.span.end_point())
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);
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 {
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
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);
195 let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| {
196 panic!("could not find statement at location {:?}
");
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); }
204 // (if there is no entry, then there are no borrows to be tracked)
208 mir::StatementKind::Assign(_, ref rhs) => {
209 if let mir::Rvalue::Ref(region, _, ref lvalue) = *rhs {
210 if is_unsafe_lvalue(self.tcx, self.mir, lvalue) { return; }
211 let index = self.location_map.get(&location).unwrap_or_else(|| {
212 panic!("could not find BorrowIndex
for location {:?}
", location);
214 assert!(self.region_map.get(region).unwrap_or_else(|| {
215 panic!("could not find BorrowIndexs
for region {:?}
", region);
216 }).contains(&index));
221 mir::StatementKind::InlineAsm { .. } |
222 mir::StatementKind::SetDiscriminant { .. } |
223 mir::StatementKind::StorageLive(..) |
224 mir::StatementKind::StorageDead(..) |
225 mir::StatementKind::Validate(..) |
226 mir::StatementKind::Nop => {}
230 self.kill_loans_out_of_scope_at_location(sets, location);
233 fn terminator_effect(&self,
234 sets: &mut BlockSets<BorrowIndex>,
235 location: Location) {
236 self.kill_loans_out_of_scope_at_location(sets, location);
239 fn propagate_call_return(&self,
240 _in_out: &mut IdxSet<BorrowIndex>,
241 _call_bb: mir::BasicBlock,
242 _dest_bb: mir::BasicBlock,
243 _dest_lval: &mir::Lvalue) {
244 // there are no effects on the region scopes from method calls.
248 impl<'a, 'gcx, 'tcx> BitwiseOperator for Borrows<'a, 'gcx, 'tcx> {
250 fn join(&self, pred1: usize, pred2: usize) -> usize {
251 pred1 | pred2 // union effects of preds when computing borrows
255 impl<'a, 'gcx, 'tcx> DataflowOperator for Borrows<'a, 'gcx, 'tcx> {
257 fn bottom_value() -> bool {
258 false // bottom = no Rvalue::Refs are active by default
262 fn is_unsafe_lvalue<'a, 'gcx: 'tcx, 'tcx: 'a>(
263 tcx: TyCtxt<'a, 'gcx, 'tcx>,
265 lvalue: &mir::Lvalue<'tcx>
267 use self::mir::Lvalue::*;
268 use self::mir::ProjectionElem;
272 Static(ref static_) => tcx.is_static_mut(static_.def_id),
273 Projection(ref proj) => {
275 ProjectionElem::Field(..) |
276 ProjectionElem::Downcast(..) |
277 ProjectionElem::Subslice { .. } |
278 ProjectionElem::ConstantIndex { .. } |
279 ProjectionElem::Index(_) => {
280 is_unsafe_lvalue(tcx, mir, &proj.base)
282 ProjectionElem::Deref => {
283 let ty = proj.base.ty(mir, tcx).to_ty(tcx);
285 ty::TyRawPtr(..) => true,
286 _ => is_unsafe_lvalue(tcx, mir, &proj.base),