1 use crate::borrow_check::nll::ToRegionVid;
2 use crate::borrow_check::path_utils::allow_two_phase_borrow;
3 use crate::borrow_check::place_ext::PlaceExt;
4 use crate::dataflow::indexes::BorrowIndex;
5 use crate::dataflow::move_paths::MoveData;
6 use rustc::mir::traversal;
7 use rustc::mir::visit::{MutatingUseContext, NonUseContext, PlaceContext, Visitor};
8 use rustc::mir::{self, Body, Local, Location, ReadOnlyBodyAndCache};
9 use rustc::ty::{RegionVid, TyCtxt};
10 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
11 use rustc_index::bit_set::BitSet;
12 use rustc_index::vec::IndexVec;
16 crate struct BorrowSet<'tcx> {
17 /// The fundamental map relating bitvector indexes to the borrows
19 crate borrows: IndexVec<BorrowIndex, BorrowData<'tcx>>,
21 /// Each borrow is also uniquely identified in the MIR by the
22 /// `Location` of the assignment statement in which it appears on
23 /// the right hand side; we map each such location to the
24 /// corresponding `BorrowIndex`.
25 crate location_map: FxHashMap<Location, BorrowIndex>,
27 /// Locations which activate borrows.
28 /// NOTE: a given location may activate more than one borrow in the future
29 /// when more general two-phase borrow support is introduced, but for now we
30 /// only need to store one borrow index.
31 crate activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
33 /// Map from local to all the borrows on that local.
34 crate local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
36 crate locals_state_at_exit: LocalsStateAtExit,
39 impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> {
40 type Output = BorrowData<'tcx>;
42 fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> {
47 /// Location where a two-phase borrow is activated, if a borrow
48 /// is in fact a two-phase borrow.
49 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
50 crate enum TwoPhaseActivation {
53 ActivatedAt(Location),
56 #[derive(Debug, Clone)]
57 crate struct BorrowData<'tcx> {
58 /// Location where the borrow reservation starts.
59 /// In many cases, this will be equal to the activation location but not always.
60 crate reserve_location: Location,
61 /// Location where the borrow is activated.
62 crate activation_location: TwoPhaseActivation,
63 /// What kind of borrow this is
64 crate kind: mir::BorrowKind,
65 /// The region for which this borrow is live
66 crate region: RegionVid,
67 /// Place from which we are borrowing
68 crate borrowed_place: mir::Place<'tcx>,
69 /// Place to which the borrow was stored
70 crate assigned_place: mir::Place<'tcx>,
73 impl<'tcx> fmt::Display for BorrowData<'tcx> {
74 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
75 let kind = match self.kind {
76 mir::BorrowKind::Shared => "",
77 mir::BorrowKind::Shallow => "shallow ",
78 mir::BorrowKind::Unique => "uniq ",
79 mir::BorrowKind::Mut { .. } => "mut ",
81 write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place)
85 crate enum LocalsStateAtExit {
87 SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> },
90 impl LocalsStateAtExit {
92 locals_are_invalidated_at_exit: bool,
93 body: ReadOnlyBodyAndCache<'_, 'tcx>,
94 move_data: &MoveData<'tcx>,
96 struct HasStorageDead(BitSet<Local>);
98 impl<'tcx> Visitor<'tcx> for HasStorageDead {
99 fn visit_local(&mut self, local: &Local, ctx: PlaceContext, _: Location) {
100 if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) {
101 self.0.insert(*local);
106 if locals_are_invalidated_at_exit {
107 LocalsStateAtExit::AllAreInvalidated
109 let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len()));
110 has_storage_dead.visit_body(body);
111 let mut has_storage_dead_or_moved = has_storage_dead.0;
112 for move_out in &move_data.moves {
113 if let Some(index) = move_data.base_local(move_out.path) {
114 has_storage_dead_or_moved.insert(index);
117 LocalsStateAtExit::SomeAreInvalidated { has_storage_dead_or_moved }
122 impl<'tcx> BorrowSet<'tcx> {
125 body: ReadOnlyBodyAndCache<'_, 'tcx>,
126 locals_are_invalidated_at_exit: bool,
127 move_data: &MoveData<'tcx>,
129 let mut visitor = GatherBorrows {
132 idx_vec: IndexVec::new(),
133 location_map: Default::default(),
134 activation_map: Default::default(),
135 local_map: Default::default(),
136 pending_activations: Default::default(),
137 locals_state_at_exit: LocalsStateAtExit::build(
138 locals_are_invalidated_at_exit,
144 for (block, block_data) in traversal::preorder(&body) {
145 visitor.visit_basic_block_data(block, block_data);
149 borrows: visitor.idx_vec,
150 location_map: visitor.location_map,
151 activation_map: visitor.activation_map,
152 local_map: visitor.local_map,
153 locals_state_at_exit: visitor.locals_state_at_exit,
157 crate fn activations_at_location(&self, location: Location) -> &[BorrowIndex] {
158 self.activation_map.get(&location).map(|activations| &activations[..]).unwrap_or(&[])
162 struct GatherBorrows<'a, 'tcx> {
164 body: &'a Body<'tcx>,
165 idx_vec: IndexVec<BorrowIndex, BorrowData<'tcx>>,
166 location_map: FxHashMap<Location, BorrowIndex>,
167 activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
168 local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
170 /// When we encounter a 2-phase borrow statement, it will always
171 /// be assigning into a temporary TEMP:
175 /// We add TEMP into this map with `b`, where `b` is the index of
176 /// the borrow. When we find a later use of this activation, we
177 /// remove from the map (and add to the "tombstone" set below).
178 pending_activations: FxHashMap<mir::Local, BorrowIndex>,
180 locals_state_at_exit: LocalsStateAtExit,
183 impl<'a, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'tcx> {
186 assigned_place: &mir::Place<'tcx>,
187 rvalue: &mir::Rvalue<'tcx>,
188 location: mir::Location,
190 if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue {
191 if borrowed_place.ignore_borrow(self.tcx, self.body, &self.locals_state_at_exit) {
192 debug!("ignoring_borrow of {:?}", borrowed_place);
196 let region = region.to_region_vid();
198 let borrow = BorrowData {
201 reserve_location: location,
202 activation_location: TwoPhaseActivation::NotTwoPhase,
203 borrowed_place: *borrowed_place,
204 assigned_place: *assigned_place,
206 let idx = self.idx_vec.push(borrow);
207 self.location_map.insert(location, idx);
209 self.insert_as_pending_if_two_phase(location, &assigned_place, kind, idx);
211 self.local_map.entry(borrowed_place.local).or_default().insert(idx);
214 self.super_assign(assigned_place, rvalue, location)
217 fn visit_local(&mut self, temp: &Local, context: PlaceContext, location: Location) {
218 if !context.is_use() {
222 // We found a use of some temporary TMP
223 // check whether we (earlier) saw a 2-phase borrow like
226 if let Some(&borrow_index) = self.pending_activations.get(temp) {
227 let borrow_data = &mut self.idx_vec[borrow_index];
229 // Watch out: the use of TMP in the borrow itself
230 // doesn't count as an activation. =)
231 if borrow_data.reserve_location == location
232 && context == PlaceContext::MutatingUse(MutatingUseContext::Store)
237 if let TwoPhaseActivation::ActivatedAt(other_location) = borrow_data.activation_location
240 self.body.source_info(location).span,
241 "found two uses for 2-phase borrow temporary {:?}: \
249 // Otherwise, this is the unique later use that we expect.
250 // Double check: This borrow is indeed a two-phase borrow (that is,
251 // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and
252 // we've not found any other activations (checked above).
254 borrow_data.activation_location,
255 TwoPhaseActivation::NotActivated,
256 "never found an activation for this borrow!",
258 self.activation_map.entry(location).or_default().push(borrow_index);
260 borrow_data.activation_location = TwoPhaseActivation::ActivatedAt(location);
264 fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location) {
265 if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue {
266 // double-check that we already registered a BorrowData for this
268 let borrow_index = self.location_map[&location];
269 let borrow_data = &self.idx_vec[borrow_index];
270 assert_eq!(borrow_data.reserve_location, location);
271 assert_eq!(borrow_data.kind, kind);
272 assert_eq!(borrow_data.region, region.to_region_vid());
273 assert_eq!(borrow_data.borrowed_place, *place);
276 return self.super_rvalue(rvalue, location);
280 impl<'a, 'tcx> GatherBorrows<'a, 'tcx> {
281 /// If this is a two-phase borrow, then we will record it
282 /// as "pending" until we find the activating use.
283 fn insert_as_pending_if_two_phase(
285 start_location: Location,
286 assigned_place: &mir::Place<'tcx>,
287 kind: mir::BorrowKind,
288 borrow_index: BorrowIndex,
291 "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})",
292 start_location, assigned_place, borrow_index,
295 if !allow_two_phase_borrow(kind) {
296 debug!(" -> {:?}", start_location);
300 // When we encounter a 2-phase borrow statement, it will always
301 // be assigning into a temporary TEMP:
305 // so extract `temp`.
306 let temp = if let Some(temp) = assigned_place.as_local() {
310 self.body.source_info(start_location).span,
311 "expected 2-phase borrow to assign to a local, not `{:?}`",
316 // Consider the borrow not activated to start. When we find an activation, we'll update
319 let borrow_data = &mut self.idx_vec[borrow_index];
320 borrow_data.activation_location = TwoPhaseActivation::NotActivated;
323 // Insert `temp` into the list of pending activations. From
324 // now on, we'll be on the lookout for a use of it. Note that
325 // we are guaranteed that this use will come after the
327 let old_value = self.pending_activations.insert(temp, borrow_index);
328 if let Some(old_index) = old_value {
330 self.body.source_info(start_location).span,
331 "found already pending activation for temp: {:?} \
332 at borrow_index: {:?} with associated data {:?}",
335 self.idx_vec[old_index]