1 #![deny(rustc::untranslatable_diagnostic)]
2 #![deny(rustc::diagnostic_outside_of_impl)]
3 use crate::nll::ToRegionVid;
4 use crate::path_utils::allow_two_phase_borrow;
5 use crate::place_ext::PlaceExt;
6 use crate::BorrowIndex;
7 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap};
8 use rustc_index::bit_set::BitSet;
9 use rustc_middle::mir::traversal;
10 use rustc_middle::mir::visit::{MutatingUseContext, NonUseContext, PlaceContext, Visitor};
11 use rustc_middle::mir::{self, Body, Local, Location};
12 use rustc_middle::ty::{RegionVid, TyCtxt};
13 use rustc_mir_dataflow::move_paths::MoveData;
17 pub struct BorrowSet<'tcx> {
18 /// The fundamental map relating bitvector indexes to the borrows
19 /// in the MIR. Each borrow is also uniquely identified in the MIR
20 /// by the `Location` of the assignment statement in which it
21 /// appears on the right hand side. Thus the location is the map
22 /// key, and its position in the map corresponds to `BorrowIndex`.
23 pub location_map: FxIndexMap<Location, BorrowData<'tcx>>,
25 /// Locations which activate borrows.
26 /// NOTE: a given location may activate more than one borrow in the future
27 /// when more general two-phase borrow support is introduced, but for now we
28 /// only need to store one borrow index.
29 pub activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
31 /// Map from local to all the borrows on that local.
32 pub local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
34 pub(crate) locals_state_at_exit: LocalsStateAtExit,
37 impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> {
38 type Output = BorrowData<'tcx>;
40 fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> {
41 &self.location_map[index.as_usize()]
45 /// Location where a two-phase borrow is activated, if a borrow
46 /// is in fact a two-phase borrow.
47 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
48 pub enum TwoPhaseActivation {
51 ActivatedAt(Location),
54 #[derive(Debug, Clone)]
55 pub struct BorrowData<'tcx> {
56 /// Location where the borrow reservation starts.
57 /// In many cases, this will be equal to the activation location but not always.
58 pub reserve_location: Location,
59 /// Location where the borrow is activated.
60 pub activation_location: TwoPhaseActivation,
61 /// What kind of borrow this is
62 pub kind: mir::BorrowKind,
63 /// The region for which this borrow is live
64 pub region: RegionVid,
65 /// Place from which we are borrowing
66 pub borrowed_place: mir::Place<'tcx>,
67 /// Place to which the borrow was stored
68 pub assigned_place: mir::Place<'tcx>,
71 impl<'tcx> fmt::Display for BorrowData<'tcx> {
72 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
73 let kind = match self.kind {
74 mir::BorrowKind::Shared => "",
75 mir::BorrowKind::Shallow => "shallow ",
76 mir::BorrowKind::Unique => "uniq ",
77 mir::BorrowKind::Mut { .. } => "mut ",
79 write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place)
83 pub enum LocalsStateAtExit {
85 SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> },
88 impl LocalsStateAtExit {
90 locals_are_invalidated_at_exit: bool,
92 move_data: &MoveData<'tcx>,
94 struct HasStorageDead(BitSet<Local>);
96 impl<'tcx> Visitor<'tcx> for HasStorageDead {
97 fn visit_local(&mut self, local: Local, ctx: PlaceContext, _: Location) {
98 if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) {
104 if locals_are_invalidated_at_exit {
105 LocalsStateAtExit::AllAreInvalidated
107 let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len()));
108 has_storage_dead.visit_body(&body);
109 let mut has_storage_dead_or_moved = has_storage_dead.0;
110 for move_out in &move_data.moves {
111 if let Some(index) = move_data.base_local(move_out.path) {
112 has_storage_dead_or_moved.insert(index);
115 LocalsStateAtExit::SomeAreInvalidated { has_storage_dead_or_moved }
120 impl<'tcx> BorrowSet<'tcx> {
124 locals_are_invalidated_at_exit: bool,
125 move_data: &MoveData<'tcx>,
127 let mut visitor = GatherBorrows {
130 location_map: Default::default(),
131 activation_map: Default::default(),
132 local_map: Default::default(),
133 pending_activations: Default::default(),
134 locals_state_at_exit: LocalsStateAtExit::build(
135 locals_are_invalidated_at_exit,
141 for (block, block_data) in traversal::preorder(&body) {
142 visitor.visit_basic_block_data(block, block_data);
146 location_map: visitor.location_map,
147 activation_map: visitor.activation_map,
148 local_map: visitor.local_map,
149 locals_state_at_exit: visitor.locals_state_at_exit,
153 pub(crate) fn activations_at_location(&self, location: Location) -> &[BorrowIndex] {
154 self.activation_map.get(&location).map_or(&[], |activations| &activations[..])
157 pub(crate) fn len(&self) -> usize {
158 self.location_map.len()
161 pub(crate) fn indices(&self) -> impl Iterator<Item = BorrowIndex> {
162 BorrowIndex::from_usize(0)..BorrowIndex::from_usize(self.len())
165 pub(crate) fn iter_enumerated(&self) -> impl Iterator<Item = (BorrowIndex, &BorrowData<'tcx>)> {
166 self.indices().zip(self.location_map.values())
169 pub(crate) fn get_index_of(&self, location: &Location) -> Option<BorrowIndex> {
170 self.location_map.get_index_of(location).map(BorrowIndex::from)
174 struct GatherBorrows<'a, 'tcx> {
176 body: &'a Body<'tcx>,
177 location_map: FxIndexMap<Location, BorrowData<'tcx>>,
178 activation_map: FxHashMap<Location, Vec<BorrowIndex>>,
179 local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,
181 /// When we encounter a 2-phase borrow statement, it will always
182 /// be assigning into a temporary TEMP:
186 /// We add TEMP into this map with `b`, where `b` is the index of
187 /// the borrow. When we find a later use of this activation, we
188 /// remove from the map (and add to the "tombstone" set below).
189 pending_activations: FxHashMap<mir::Local, BorrowIndex>,
191 locals_state_at_exit: LocalsStateAtExit,
194 impl<'a, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'tcx> {
197 assigned_place: &mir::Place<'tcx>,
198 rvalue: &mir::Rvalue<'tcx>,
199 location: mir::Location,
201 if let &mir::Rvalue::Ref(region, kind, borrowed_place) = rvalue {
202 if borrowed_place.ignore_borrow(self.tcx, self.body, &self.locals_state_at_exit) {
203 debug!("ignoring_borrow of {:?}", borrowed_place);
207 let region = region.to_region_vid();
209 let borrow = BorrowData {
212 reserve_location: location,
213 activation_location: TwoPhaseActivation::NotTwoPhase,
215 assigned_place: *assigned_place,
217 let (idx, _) = self.location_map.insert_full(location, borrow);
218 let idx = BorrowIndex::from(idx);
220 self.insert_as_pending_if_two_phase(location, assigned_place, kind, idx);
222 self.local_map.entry(borrowed_place.local).or_default().insert(idx);
225 self.super_assign(assigned_place, rvalue, location)
228 fn visit_local(&mut self, temp: Local, context: PlaceContext, location: Location) {
229 if !context.is_use() {
233 // We found a use of some temporary TMP
234 // check whether we (earlier) saw a 2-phase borrow like
237 if let Some(&borrow_index) = self.pending_activations.get(&temp) {
238 let borrow_data = &mut self.location_map[borrow_index.as_usize()];
240 // Watch out: the use of TMP in the borrow itself
241 // doesn't count as an activation. =)
242 if borrow_data.reserve_location == location
243 && context == PlaceContext::MutatingUse(MutatingUseContext::Store)
248 if let TwoPhaseActivation::ActivatedAt(other_location) = borrow_data.activation_location
251 self.body.source_info(location).span,
252 "found two uses for 2-phase borrow temporary {:?}: \
260 // Otherwise, this is the unique later use that we expect.
261 // Double check: This borrow is indeed a two-phase borrow (that is,
262 // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and
263 // we've not found any other activations (checked above).
265 borrow_data.activation_location,
266 TwoPhaseActivation::NotActivated,
267 "never found an activation for this borrow!",
269 self.activation_map.entry(location).or_default().push(borrow_index);
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, place) = rvalue {
277 // double-check that we already registered a BorrowData for this
279 let borrow_data = &self.location_map[&location];
280 assert_eq!(borrow_data.reserve_location, location);
281 assert_eq!(borrow_data.kind, kind);
282 assert_eq!(borrow_data.region, region.to_region_vid());
283 assert_eq!(borrow_data.borrowed_place, place);
286 self.super_rvalue(rvalue, location)
290 impl<'a, 'tcx> GatherBorrows<'a, 'tcx> {
291 /// If this is a two-phase borrow, then we will record it
292 /// as "pending" until we find the activating use.
293 fn insert_as_pending_if_two_phase(
295 start_location: Location,
296 assigned_place: &mir::Place<'tcx>,
297 kind: mir::BorrowKind,
298 borrow_index: BorrowIndex,
301 "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})",
302 start_location, assigned_place, borrow_index,
305 if !allow_two_phase_borrow(kind) {
306 debug!(" -> {:?}", start_location);
310 // When we encounter a 2-phase borrow statement, it will always
311 // be assigning into a temporary TEMP:
315 // so extract `temp`.
316 let Some(temp) = assigned_place.as_local() else {
318 self.body.source_info(start_location).span,
319 "expected 2-phase borrow to assign to a local, not `{:?}`",
324 // Consider the borrow not activated to start. When we find an activation, we'll update
327 let borrow_data = &mut self.location_map[borrow_index.as_usize()];
328 borrow_data.activation_location = TwoPhaseActivation::NotActivated;
331 // Insert `temp` into the list of pending activations. From
332 // now on, we'll be on the lookout for a use of it. Note that
333 // we are guaranteed that this use will come after the
335 let old_value = self.pending_activations.insert(temp, borrow_index);
336 if let Some(old_index) = old_value {
338 self.body.source_info(start_location).span,
339 "found already pending activation for temp: {:?} \
340 at borrow_index: {:?} with associated data {:?}",
343 self.location_map[old_index.as_usize()]