1 use crate::borrow_check::place_ext::PlaceExt;
2 use crate::borrow_check::nll::ToRegionVid;
3 use crate::dataflow::indexes::BorrowIndex;
4 use crate::dataflow::move_paths::MoveData;
5 use rustc::mir::traversal;
6 use rustc::mir::visit::{PlaceContext, Visitor, NonUseContext, MutatingUseContext};
7 use rustc::mir::{self, Location, Mir, Local};
8 use rustc::ty::{RegionVid, TyCtxt};
9 use rustc::util::nodemap::{FxHashMap, FxHashSet};
10 use rustc_data_structures::indexed_vec::IndexVec;
11 use rustc_data_structures::bit_set::BitSet;
15 crate struct BorrowSet<'tcx> {
16 /// The fundamental map relating bitvector indexes to the borrows
18 crate borrows: IndexVec<BorrowIndex, BorrowData<'tcx>>,
20 /// Each borrow is also uniquely identified in the MIR by the
21 /// `Location` of the assignment statement in which it appears on
22 /// the right hand side; we map each such location to the
23 /// corresponding `BorrowIndex`.
24 crate location_map: FxHashMap<Location, BorrowIndex>,
26 /// Locations which activate borrows.
27 /// NOTE: a given location may activate more than one borrow in the future
28 /// when more general two-phase borrow support is introduced, but for now we
29 /// only need to store one borrow index.
30 crate activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
32 /// Map from local to all the borrows on that local.
33 crate local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
35 crate locals_state_at_exit: LocalsStateAtExit,
38 impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> {
39 type Output = BorrowData<'tcx>;
41 fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> {
46 /// Location where a two-phase borrow is activated, if a borrow
47 /// is in fact a two-phase borrow.
48 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
49 crate enum TwoPhaseActivation {
52 ActivatedAt(Location),
55 #[derive(Debug, Clone)]
56 crate struct BorrowData<'tcx> {
57 /// Location where the borrow reservation starts.
58 /// In many cases, this will be equal to the activation location but not always.
59 crate reserve_location: Location,
60 /// Location where the borrow is activated.
61 crate activation_location: TwoPhaseActivation,
62 /// What kind of borrow this is
63 crate kind: mir::BorrowKind,
64 /// The region for which this borrow is live
65 crate region: RegionVid,
66 /// Place from which we are borrowing
67 crate borrowed_place: mir::Place<'tcx>,
68 /// Place to which the borrow was stored
69 crate assigned_place: mir::Place<'tcx>,
72 impl<'tcx> fmt::Display for BorrowData<'tcx> {
73 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
74 let kind = match self.kind {
75 mir::BorrowKind::Shared => "",
76 mir::BorrowKind::Shallow => "shallow ",
77 mir::BorrowKind::Unique => "uniq ",
78 mir::BorrowKind::Mut { .. } => "mut ",
80 write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place)
84 crate enum LocalsStateAtExit {
86 SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }
89 impl LocalsStateAtExit {
91 locals_are_invalidated_at_exit: bool,
93 move_data: &MoveData<'tcx>
95 struct HasStorageDead(BitSet<Local>);
97 impl<'tcx> Visitor<'tcx> for HasStorageDead {
98 fn visit_local(&mut self, local: &Local, ctx: PlaceContext<'tcx>, _: Location) {
99 if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) {
100 self.0.insert(*local);
105 if locals_are_invalidated_at_exit {
106 LocalsStateAtExit::AllAreInvalidated
108 let mut has_storage_dead = HasStorageDead(BitSet::new_empty(mir.local_decls.len()));
109 has_storage_dead.visit_mir(mir);
110 let mut has_storage_dead_or_moved = has_storage_dead.0;
111 for move_out in &move_data.moves {
112 if let Some(index) = move_data.base_local(move_out.path) {
113 has_storage_dead_or_moved.insert(index);
117 LocalsStateAtExit::SomeAreInvalidated{ has_storage_dead_or_moved }
122 impl<'tcx> BorrowSet<'tcx> {
124 tcx: TyCtxt<'_, '_, 'tcx>,
126 locals_are_invalidated_at_exit: bool,
127 move_data: &MoveData<'tcx>
130 let mut visitor = GatherBorrows {
133 idx_vec: IndexVec::new(),
134 location_map: Default::default(),
135 activation_map: Default::default(),
136 local_map: Default::default(),
137 pending_activations: Default::default(),
138 locals_state_at_exit:
139 LocalsStateAtExit::build(locals_are_invalidated_at_exit, mir, move_data),
142 for (block, block_data) in traversal::preorder(mir) {
143 visitor.visit_basic_block_data(block, block_data);
147 borrows: visitor.idx_vec,
148 location_map: visitor.location_map,
149 activation_map: visitor.activation_map,
150 local_map: visitor.local_map,
151 locals_state_at_exit: visitor.locals_state_at_exit,
155 crate fn activations_at_location(&self, location: Location) -> &[BorrowIndex] {
158 .map(|activations| &activations[..])
163 struct GatherBorrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
164 tcx: TyCtxt<'a, 'gcx, 'tcx>,
166 idx_vec: IndexVec<BorrowIndex, BorrowData<'tcx>>,
167 location_map: FxHashMap<Location, BorrowIndex>,
168 activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
169 local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
171 /// When we encounter a 2-phase borrow statement, it will always
172 /// be assigning into a temporary TEMP:
176 /// We add TEMP into this map with `b`, where `b` is the index of
177 /// the borrow. When we find a later use of this activation, we
178 /// remove from the map (and add to the "tombstone" set below).
179 pending_activations: FxHashMap<mir::Local, BorrowIndex>,
181 locals_state_at_exit: LocalsStateAtExit,
184 impl<'a, 'gcx, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'gcx, 'tcx> {
187 assigned_place: &mir::Place<'tcx>,
188 rvalue: &mir::Rvalue<'tcx>,
189 location: mir::Location,
191 if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue {
192 if borrowed_place.ignore_borrow(
193 self.tcx, self.mir, &self.locals_state_at_exit) {
197 let region = region.to_region_vid();
199 let borrow = BorrowData {
202 reserve_location: location,
203 activation_location: TwoPhaseActivation::NotTwoPhase,
204 borrowed_place: borrowed_place.clone(),
205 assigned_place: assigned_place.clone(),
207 let idx = self.idx_vec.push(borrow);
208 self.location_map.insert(location, idx);
210 self.insert_as_pending_if_two_phase(location, &assigned_place, kind, idx);
212 if let Some(local) = borrowed_place.root_local() {
213 self.local_map.entry(local).or_default().insert(idx);
217 self.super_assign(assigned_place, rvalue, location)
223 context: PlaceContext<'tcx>,
226 if !context.is_use() {
230 // We found a use of some temporary TMP
231 // check whether we (earlier) saw a 2-phase borrow like
234 if let Some(&borrow_index) = self.pending_activations.get(temp) {
235 let borrow_data = &mut self.idx_vec[borrow_index];
237 // Watch out: the use of TMP in the borrow itself
238 // doesn't count as an activation. =)
239 if borrow_data.reserve_location == location &&
240 context == PlaceContext::MutatingUse(MutatingUseContext::Store)
245 if let TwoPhaseActivation::ActivatedAt(other_location) =
246 borrow_data.activation_location {
248 self.mir.source_info(location).span,
249 "found two uses for 2-phase borrow temporary {:?}: \
257 // Otherwise, this is the unique later use that we expect.
258 // Double check: This borrow is indeed a two-phase borrow (that is,
259 // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and
260 // we've not found any other activations (checked above).
262 borrow_data.activation_location,
263 TwoPhaseActivation::NotActivated,
264 "never found an activation for this borrow!",
271 borrow_data.activation_location = TwoPhaseActivation::ActivatedAt(location);
275 fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location) {
276 if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue {
277 // double-check that we already registered a BorrowData for this
279 let borrow_index = self.location_map[&location];
280 let borrow_data = &self.idx_vec[borrow_index];
281 assert_eq!(borrow_data.reserve_location, location);
282 assert_eq!(borrow_data.kind, kind);
283 assert_eq!(borrow_data.region, region.to_region_vid());
284 assert_eq!(borrow_data.borrowed_place, *place);
287 return self.super_rvalue(rvalue, location);
291 impl<'a, 'gcx, 'tcx> GatherBorrows<'a, 'gcx, 'tcx> {
292 /// Returns `true` if the borrow represented by `kind` is
293 /// allowed to be split into separate Reservation and
294 /// Activation phases.
295 fn allow_two_phase_borrow(&self, kind: mir::BorrowKind) -> bool {
296 kind.allows_two_phase_borrow()
297 || self.tcx.sess.opts.debugging_opts.two_phase_beyond_autoref
300 /// If this is a two-phase borrow, then we will record it
301 /// as "pending" until we find the activating use.
302 fn insert_as_pending_if_two_phase(
304 start_location: Location,
305 assigned_place: &mir::Place<'tcx>,
306 kind: mir::BorrowKind,
307 borrow_index: BorrowIndex,
310 "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})",
311 start_location, assigned_place, borrow_index,
314 if !self.allow_two_phase_borrow(kind) {
315 debug!(" -> {:?}", start_location);
319 // When we encounter a 2-phase borrow statement, it will always
320 // be assigning into a temporary TEMP:
324 // so extract `temp`.
325 let temp = if let &mir::Place::Base(mir::PlaceBase::Local(temp)) = assigned_place {
329 self.mir.source_info(start_location).span,
330 "expected 2-phase borrow to assign to a local, not `{:?}`",
335 // Consider the borrow not activated to start. When we find an activation, we'll update
338 let borrow_data = &mut self.idx_vec[borrow_index];
339 borrow_data.activation_location = TwoPhaseActivation::NotActivated;
342 // Insert `temp` into the list of pending activations. From
343 // now on, we'll be on the lookout for a use of it. Note that
344 // we are guaranteed that this use will come after the
346 let old_value = self.pending_activations.insert(temp, borrow_index);
347 if let Some(old_index) = old_value {
348 span_bug!(self.mir.source_info(start_location).span,
349 "found already pending activation for temp: {:?} \
350 at borrow_index: {:?} with associated data {:?}",
351 temp, old_index, self.idx_vec[old_index]);