]>
Commit | Line | Data |
---|---|---|
c295e0f8 XL |
1 | use crate::nll::ToRegionVid; |
2 | use crate::path_utils::allow_two_phase_borrow; | |
3 | use crate::place_ext::PlaceExt; | |
4 | use crate::BorrowIndex; | |
3dfed10e | 5 | use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap}; |
e74abb32 | 6 | use rustc_index::bit_set::BitSet; |
ba9703b0 XL |
7 | use rustc_middle::mir::traversal; |
8 | use rustc_middle::mir::visit::{MutatingUseContext, NonUseContext, PlaceContext, Visitor}; | |
f9f354fc | 9 | use rustc_middle::mir::{self, Body, Local, Location}; |
ba9703b0 | 10 | use rustc_middle::ty::{RegionVid, TyCtxt}; |
c295e0f8 | 11 | use rustc_mir_dataflow::move_paths::MoveData; |
83c7162d | 12 | use std::fmt; |
83c7162d XL |
13 | use std::ops::Index; |
14 | ||
3c0e092e | 15 | pub struct BorrowSet<'tcx> { |
83c7162d | 16 | /// The fundamental map relating bitvector indexes to the borrows |
3dfed10e XL |
17 | /// in the MIR. Each borrow is also uniquely identified in the MIR |
18 | /// by the `Location` of the assignment statement in which it | |
19 | /// appears on the right hand side. Thus the location is the map | |
20 | /// key, and its position in the map corresponds to `BorrowIndex`. | |
3c0e092e | 21 | pub location_map: FxIndexMap<Location, BorrowData<'tcx>>, |
83c7162d XL |
22 | |
23 | /// Locations which activate borrows. | |
9fa01778 | 24 | /// NOTE: a given location may activate more than one borrow in the future |
83c7162d | 25 | /// when more general two-phase borrow support is introduced, but for now we |
9fa01778 | 26 | /// only need to store one borrow index. |
3c0e092e | 27 | pub activation_map: FxHashMap<Location, Vec<BorrowIndex>>, |
83c7162d | 28 | |
9fa01778 | 29 | /// Map from local to all the borrows on that local. |
3c0e092e | 30 | pub local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>, |
b7449926 XL |
31 | |
32 | crate locals_state_at_exit: LocalsStateAtExit, | |
83c7162d XL |
33 | } |
34 | ||
35 | impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> { | |
36 | type Output = BorrowData<'tcx>; | |
37 | ||
38 | fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> { | |
3dfed10e | 39 | &self.location_map[index.as_usize()] |
83c7162d XL |
40 | } |
41 | } | |
42 | ||
9fa01778 XL |
43 | /// Location where a two-phase borrow is activated, if a borrow |
44 | /// is in fact a two-phase borrow. | |
94b46f34 | 45 | #[derive(Copy, Clone, PartialEq, Eq, Debug)] |
3c0e092e | 46 | pub enum TwoPhaseActivation { |
8faf50e0 XL |
47 | NotTwoPhase, |
48 | NotActivated, | |
49 | ActivatedAt(Location), | |
94b46f34 XL |
50 | } |
51 | ||
532ac7d7 | 52 | #[derive(Debug, Clone)] |
3c0e092e | 53 | pub struct BorrowData<'tcx> { |
83c7162d XL |
54 | /// Location where the borrow reservation starts. |
55 | /// In many cases, this will be equal to the activation location but not always. | |
3c0e092e | 56 | pub reserve_location: Location, |
8faf50e0 | 57 | /// Location where the borrow is activated. |
3c0e092e | 58 | pub activation_location: TwoPhaseActivation, |
83c7162d | 59 | /// What kind of borrow this is |
3c0e092e | 60 | pub kind: mir::BorrowKind, |
83c7162d | 61 | /// The region for which this borrow is live |
3c0e092e | 62 | pub region: RegionVid, |
83c7162d | 63 | /// Place from which we are borrowing |
3c0e092e | 64 | pub borrowed_place: mir::Place<'tcx>, |
83c7162d | 65 | /// Place to which the borrow was stored |
3c0e092e | 66 | pub assigned_place: mir::Place<'tcx>, |
83c7162d XL |
67 | } |
68 | ||
69 | impl<'tcx> fmt::Display for BorrowData<'tcx> { | |
9fa01778 | 70 | fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { |
83c7162d XL |
71 | let kind = match self.kind { |
72 | mir::BorrowKind::Shared => "", | |
0bf4aa26 | 73 | mir::BorrowKind::Shallow => "shallow ", |
83c7162d XL |
74 | mir::BorrowKind::Unique => "uniq ", |
75 | mir::BorrowKind::Mut { .. } => "mut ", | |
76 | }; | |
a1dfa0c6 | 77 | write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place) |
83c7162d XL |
78 | } |
79 | } | |
80 | ||
3c0e092e | 81 | pub enum LocalsStateAtExit { |
b7449926 | 82 | AllAreInvalidated, |
dfeec247 | 83 | SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }, |
b7449926 XL |
84 | } |
85 | ||
86 | impl LocalsStateAtExit { | |
87 | fn build( | |
88 | locals_are_invalidated_at_exit: bool, | |
f9f354fc | 89 | body: &Body<'tcx>, |
dfeec247 | 90 | move_data: &MoveData<'tcx>, |
b7449926 | 91 | ) -> Self { |
0bf4aa26 | 92 | struct HasStorageDead(BitSet<Local>); |
b7449926 XL |
93 | |
94 | impl<'tcx> Visitor<'tcx> for HasStorageDead { | |
48663c56 | 95 | fn visit_local(&mut self, local: &Local, ctx: PlaceContext, _: Location) { |
13cf67c4 | 96 | if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) { |
b7449926 XL |
97 | self.0.insert(*local); |
98 | } | |
99 | } | |
100 | } | |
101 | ||
102 | if locals_are_invalidated_at_exit { | |
103 | LocalsStateAtExit::AllAreInvalidated | |
104 | } else { | |
dfeec247 | 105 | let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len())); |
ba9703b0 | 106 | has_storage_dead.visit_body(&body); |
b7449926 XL |
107 | let mut has_storage_dead_or_moved = has_storage_dead.0; |
108 | for move_out in &move_data.moves { | |
109 | if let Some(index) = move_data.base_local(move_out.path) { | |
110 | has_storage_dead_or_moved.insert(index); | |
b7449926 XL |
111 | } |
112 | } | |
dfeec247 | 113 | LocalsStateAtExit::SomeAreInvalidated { has_storage_dead_or_moved } |
b7449926 XL |
114 | } |
115 | } | |
116 | } | |
117 | ||
83c7162d | 118 | impl<'tcx> BorrowSet<'tcx> { |
b7449926 | 119 | pub fn build( |
dc9dc135 | 120 | tcx: TyCtxt<'tcx>, |
f9f354fc | 121 | body: &Body<'tcx>, |
b7449926 | 122 | locals_are_invalidated_at_exit: bool, |
dc9dc135 | 123 | move_data: &MoveData<'tcx>, |
b7449926 | 124 | ) -> Self { |
83c7162d XL |
125 | let mut visitor = GatherBorrows { |
126 | tcx, | |
60c5eb7d | 127 | body: &body, |
0bf4aa26 XL |
128 | location_map: Default::default(), |
129 | activation_map: Default::default(), | |
0bf4aa26 XL |
130 | local_map: Default::default(), |
131 | pending_activations: Default::default(), | |
dfeec247 XL |
132 | locals_state_at_exit: LocalsStateAtExit::build( |
133 | locals_are_invalidated_at_exit, | |
134 | body, | |
135 | move_data, | |
136 | ), | |
83c7162d XL |
137 | }; |
138 | ||
60c5eb7d | 139 | for (block, block_data) in traversal::preorder(&body) { |
83c7162d XL |
140 | visitor.visit_basic_block_data(block, block_data); |
141 | } | |
142 | ||
83c7162d | 143 | BorrowSet { |
83c7162d XL |
144 | location_map: visitor.location_map, |
145 | activation_map: visitor.activation_map, | |
83c7162d | 146 | local_map: visitor.local_map, |
b7449926 | 147 | locals_state_at_exit: visitor.locals_state_at_exit, |
83c7162d XL |
148 | } |
149 | } | |
150 | ||
151 | crate fn activations_at_location(&self, location: Location) -> &[BorrowIndex] { | |
5869c6ff | 152 | self.activation_map.get(&location).map_or(&[], |activations| &activations[..]) |
83c7162d | 153 | } |
3dfed10e XL |
154 | |
155 | crate fn len(&self) -> usize { | |
156 | self.location_map.len() | |
157 | } | |
158 | ||
159 | crate fn indices(&self) -> impl Iterator<Item = BorrowIndex> { | |
160 | BorrowIndex::from_usize(0)..BorrowIndex::from_usize(self.len()) | |
161 | } | |
162 | ||
163 | crate fn iter_enumerated(&self) -> impl Iterator<Item = (BorrowIndex, &BorrowData<'tcx>)> { | |
164 | self.indices().zip(self.location_map.values()) | |
165 | } | |
166 | ||
167 | crate fn get_index_of(&self, location: &Location) -> Option<BorrowIndex> { | |
168 | self.location_map.get_index_of(location).map(BorrowIndex::from) | |
169 | } | |
170 | ||
171 | crate fn contains(&self, location: &Location) -> bool { | |
172 | self.location_map.contains_key(location) | |
173 | } | |
83c7162d XL |
174 | } |
175 | ||
dc9dc135 XL |
176 | struct GatherBorrows<'a, 'tcx> { |
177 | tcx: TyCtxt<'tcx>, | |
178 | body: &'a Body<'tcx>, | |
3dfed10e | 179 | location_map: FxIndexMap<Location, BorrowData<'tcx>>, |
83c7162d | 180 | activation_map: FxHashMap<Location, Vec<BorrowIndex>>, |
83c7162d XL |
181 | local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>, |
182 | ||
183 | /// When we encounter a 2-phase borrow statement, it will always | |
184 | /// be assigning into a temporary TEMP: | |
185 | /// | |
186 | /// TEMP = &foo | |
187 | /// | |
188 | /// We add TEMP into this map with `b`, where `b` is the index of | |
189 | /// the borrow. When we find a later use of this activation, we | |
190 | /// remove from the map (and add to the "tombstone" set below). | |
191 | pending_activations: FxHashMap<mir::Local, BorrowIndex>, | |
b7449926 XL |
192 | |
193 | locals_state_at_exit: LocalsStateAtExit, | |
83c7162d XL |
194 | } |
195 | ||
dc9dc135 | 196 | impl<'a, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'tcx> { |
83c7162d XL |
197 | fn visit_assign( |
198 | &mut self, | |
83c7162d XL |
199 | assigned_place: &mir::Place<'tcx>, |
200 | rvalue: &mir::Rvalue<'tcx>, | |
201 | location: mir::Location, | |
202 | ) { | |
203 | if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue { | |
60c5eb7d XL |
204 | if borrowed_place.ignore_borrow(self.tcx, self.body, &self.locals_state_at_exit) { |
205 | debug!("ignoring_borrow of {:?}", borrowed_place); | |
83c7162d XL |
206 | return; |
207 | } | |
208 | ||
a1dfa0c6 XL |
209 | let region = region.to_region_vid(); |
210 | ||
83c7162d XL |
211 | let borrow = BorrowData { |
212 | kind, | |
213 | region, | |
214 | reserve_location: location, | |
8faf50e0 | 215 | activation_location: TwoPhaseActivation::NotTwoPhase, |
dfeec247 XL |
216 | borrowed_place: *borrowed_place, |
217 | assigned_place: *assigned_place, | |
83c7162d | 218 | }; |
3dfed10e XL |
219 | let (idx, _) = self.location_map.insert_full(location, borrow); |
220 | let idx = BorrowIndex::from(idx); | |
83c7162d | 221 | |
ba9703b0 | 222 | self.insert_as_pending_if_two_phase(location, assigned_place, kind, idx); |
83c7162d | 223 | |
dfeec247 | 224 | self.local_map.entry(borrowed_place.local).or_default().insert(idx); |
83c7162d XL |
225 | } |
226 | ||
48663c56 | 227 | self.super_assign(assigned_place, rvalue, location) |
83c7162d XL |
228 | } |
229 | ||
dfeec247 | 230 | fn visit_local(&mut self, temp: &Local, context: PlaceContext, location: Location) { |
0731742a XL |
231 | if !context.is_use() { |
232 | return; | |
233 | } | |
83c7162d | 234 | |
0731742a XL |
235 | // We found a use of some temporary TMP |
236 | // check whether we (earlier) saw a 2-phase borrow like | |
237 | // | |
238 | // TMP = &mut place | |
239 | if let Some(&borrow_index) = self.pending_activations.get(temp) { | |
3dfed10e | 240 | let borrow_data = &mut self.location_map[borrow_index.as_usize()]; |
0731742a XL |
241 | |
242 | // Watch out: the use of TMP in the borrow itself | |
243 | // doesn't count as an activation. =) | |
dfeec247 XL |
244 | if borrow_data.reserve_location == location |
245 | && context == PlaceContext::MutatingUse(MutatingUseContext::Store) | |
0731742a XL |
246 | { |
247 | return; | |
248 | } | |
83c7162d | 249 | |
dfeec247 XL |
250 | if let TwoPhaseActivation::ActivatedAt(other_location) = borrow_data.activation_location |
251 | { | |
0731742a | 252 | span_bug!( |
dc9dc135 | 253 | self.body.source_info(location).span, |
0731742a XL |
254 | "found two uses for 2-phase borrow temporary {:?}: \ |
255 | {:?} and {:?}", | |
256 | temp, | |
257 | location, | |
258 | other_location, | |
259 | ); | |
83c7162d | 260 | } |
0731742a | 261 | |
9fa01778 XL |
262 | // Otherwise, this is the unique later use that we expect. |
263 | // Double check: This borrow is indeed a two-phase borrow (that is, | |
264 | // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and | |
265 | // we've not found any other activations (checked above). | |
266 | assert_eq!( | |
267 | borrow_data.activation_location, | |
268 | TwoPhaseActivation::NotActivated, | |
269 | "never found an activation for this borrow!", | |
270 | ); | |
dfeec247 | 271 | self.activation_map.entry(location).or_default().push(borrow_index); |
9fa01778 XL |
272 | |
273 | borrow_data.activation_location = TwoPhaseActivation::ActivatedAt(location); | |
83c7162d XL |
274 | } |
275 | } | |
276 | ||
277 | fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location) { | |
278 | if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue { | |
279 | // double-check that we already registered a BorrowData for this | |
280 | ||
3dfed10e | 281 | let borrow_data = &self.location_map[&location]; |
83c7162d XL |
282 | assert_eq!(borrow_data.reserve_location, location); |
283 | assert_eq!(borrow_data.kind, kind); | |
a1dfa0c6 | 284 | assert_eq!(borrow_data.region, region.to_region_vid()); |
83c7162d XL |
285 | assert_eq!(borrow_data.borrowed_place, *place); |
286 | } | |
287 | ||
ba9703b0 | 288 | self.super_rvalue(rvalue, location) |
83c7162d | 289 | } |
83c7162d XL |
290 | } |
291 | ||
dc9dc135 | 292 | impl<'a, 'tcx> GatherBorrows<'a, 'tcx> { |
83c7162d XL |
293 | /// If this is a two-phase borrow, then we will record it |
294 | /// as "pending" until we find the activating use. | |
295 | fn insert_as_pending_if_two_phase( | |
296 | &mut self, | |
297 | start_location: Location, | |
298 | assigned_place: &mir::Place<'tcx>, | |
83c7162d XL |
299 | kind: mir::BorrowKind, |
300 | borrow_index: BorrowIndex, | |
301 | ) { | |
302 | debug!( | |
a1dfa0c6 XL |
303 | "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})", |
304 | start_location, assigned_place, borrow_index, | |
83c7162d XL |
305 | ); |
306 | ||
48663c56 | 307 | if !allow_two_phase_borrow(kind) { |
83c7162d XL |
308 | debug!(" -> {:?}", start_location); |
309 | return; | |
310 | } | |
311 | ||
312 | // When we encounter a 2-phase borrow statement, it will always | |
313 | // be assigning into a temporary TEMP: | |
314 | // | |
315 | // TEMP = &foo | |
316 | // | |
317 | // so extract `temp`. | |
3c0e092e | 318 | let Some(temp) = assigned_place.as_local() else { |
83c7162d | 319 | span_bug!( |
dc9dc135 | 320 | self.body.source_info(start_location).span, |
83c7162d XL |
321 | "expected 2-phase borrow to assign to a local, not `{:?}`", |
322 | assigned_place, | |
323 | ); | |
324 | }; | |
325 | ||
8faf50e0 XL |
326 | // Consider the borrow not activated to start. When we find an activation, we'll update |
327 | // this field. | |
328 | { | |
3dfed10e | 329 | let borrow_data = &mut self.location_map[borrow_index.as_usize()]; |
8faf50e0 XL |
330 | borrow_data.activation_location = TwoPhaseActivation::NotActivated; |
331 | } | |
332 | ||
83c7162d XL |
333 | // Insert `temp` into the list of pending activations. From |
334 | // now on, we'll be on the lookout for a use of it. Note that | |
335 | // we are guaranteed that this use will come after the | |
336 | // assignment. | |
337 | let old_value = self.pending_activations.insert(temp, borrow_index); | |
8faf50e0 | 338 | if let Some(old_index) = old_value { |
dfeec247 XL |
339 | span_bug!( |
340 | self.body.source_info(start_location).span, | |
341 | "found already pending activation for temp: {:?} \ | |
8faf50e0 | 342 | at borrow_index: {:?} with associated data {:?}", |
dfeec247 XL |
343 | temp, |
344 | old_index, | |
3dfed10e | 345 | self.location_map[old_index.as_usize()] |
dfeec247 | 346 | ); |
8faf50e0 | 347 | } |
83c7162d XL |
348 | } |
349 | } |