]>
Commit | Line | Data |
---|---|---|
487cf647 FG |
1 | #![deny(rustc::untranslatable_diagnostic)] |
2 | #![deny(rustc::diagnostic_outside_of_impl)] | |
c295e0f8 XL |
3 | use crate::path_utils::allow_two_phase_borrow; |
4 | use crate::place_ext::PlaceExt; | |
5 | use crate::BorrowIndex; | |
353b0b11 | 6 | use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; |
e74abb32 | 7 | use rustc_index::bit_set::BitSet; |
ba9703b0 XL |
8 | use rustc_middle::mir::traversal; |
9 | use rustc_middle::mir::visit::{MutatingUseContext, NonUseContext, PlaceContext, Visitor}; | |
f9f354fc | 10 | use rustc_middle::mir::{self, Body, Local, Location}; |
ba9703b0 | 11 | use rustc_middle::ty::{RegionVid, TyCtxt}; |
c295e0f8 | 12 | use rustc_mir_dataflow::move_paths::MoveData; |
83c7162d | 13 | use std::fmt; |
83c7162d XL |
14 | use std::ops::Index; |
15 | ||
3c0e092e | 16 | pub struct BorrowSet<'tcx> { |
83c7162d | 17 | /// The fundamental map relating bitvector indexes to the borrows |
3dfed10e XL |
18 | /// in the MIR. Each borrow is also uniquely identified in the MIR |
19 | /// by the `Location` of the assignment statement in which it | |
20 | /// appears on the right hand side. Thus the location is the map | |
21 | /// key, and its position in the map corresponds to `BorrowIndex`. | |
3c0e092e | 22 | pub location_map: FxIndexMap<Location, BorrowData<'tcx>>, |
83c7162d XL |
23 | |
24 | /// Locations which activate borrows. | |
9fa01778 | 25 | /// NOTE: a given location may activate more than one borrow in the future |
83c7162d | 26 | /// when more general two-phase borrow support is introduced, but for now we |
9fa01778 | 27 | /// only need to store one borrow index. |
353b0b11 | 28 | pub activation_map: FxIndexMap<Location, Vec<BorrowIndex>>, |
83c7162d | 29 | |
9fa01778 | 30 | /// Map from local to all the borrows on that local. |
353b0b11 | 31 | pub local_map: FxIndexMap<mir::Local, FxIndexSet<BorrowIndex>>, |
b7449926 | 32 | |
49aad941 | 33 | pub locals_state_at_exit: LocalsStateAtExit, |
83c7162d XL |
34 | } |
35 | ||
36 | impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> { | |
37 | type Output = BorrowData<'tcx>; | |
38 | ||
39 | fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> { | |
3dfed10e | 40 | &self.location_map[index.as_usize()] |
83c7162d XL |
41 | } |
42 | } | |
43 | ||
9fa01778 XL |
44 | /// Location where a two-phase borrow is activated, if a borrow |
45 | /// is in fact a two-phase borrow. | |
94b46f34 | 46 | #[derive(Copy, Clone, PartialEq, Eq, Debug)] |
3c0e092e | 47 | pub enum TwoPhaseActivation { |
8faf50e0 XL |
48 | NotTwoPhase, |
49 | NotActivated, | |
50 | ActivatedAt(Location), | |
94b46f34 XL |
51 | } |
52 | ||
532ac7d7 | 53 | #[derive(Debug, Clone)] |
3c0e092e | 54 | pub struct BorrowData<'tcx> { |
83c7162d XL |
55 | /// Location where the borrow reservation starts. |
56 | /// In many cases, this will be equal to the activation location but not always. | |
3c0e092e | 57 | pub reserve_location: Location, |
8faf50e0 | 58 | /// Location where the borrow is activated. |
3c0e092e | 59 | pub activation_location: TwoPhaseActivation, |
83c7162d | 60 | /// What kind of borrow this is |
3c0e092e | 61 | pub kind: mir::BorrowKind, |
83c7162d | 62 | /// The region for which this borrow is live |
3c0e092e | 63 | pub region: RegionVid, |
83c7162d | 64 | /// Place from which we are borrowing |
3c0e092e | 65 | pub borrowed_place: mir::Place<'tcx>, |
83c7162d | 66 | /// Place to which the borrow was stored |
3c0e092e | 67 | pub assigned_place: mir::Place<'tcx>, |
83c7162d XL |
68 | } |
69 | ||
70 | impl<'tcx> fmt::Display for BorrowData<'tcx> { | |
9fa01778 | 71 | fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { |
83c7162d XL |
72 | let kind = match self.kind { |
73 | mir::BorrowKind::Shared => "", | |
0bf4aa26 | 74 | mir::BorrowKind::Shallow => "shallow ", |
fe692bf9 FG |
75 | mir::BorrowKind::Mut { kind: mir::MutBorrowKind::ClosureCapture } => "uniq ", |
76 | // FIXME: differentiate `TwoPhaseBorrow` | |
77 | mir::BorrowKind::Mut { | |
78 | kind: mir::MutBorrowKind::Default | mir::MutBorrowKind::TwoPhaseBorrow, | |
79 | } => "mut ", | |
83c7162d | 80 | }; |
a1dfa0c6 | 81 | write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place) |
83c7162d XL |
82 | } |
83 | } | |
84 | ||
3c0e092e | 85 | pub enum LocalsStateAtExit { |
b7449926 | 86 | AllAreInvalidated, |
dfeec247 | 87 | SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }, |
b7449926 XL |
88 | } |
89 | ||
90 | impl LocalsStateAtExit { | |
a2a8927a | 91 | fn build<'tcx>( |
b7449926 | 92 | locals_are_invalidated_at_exit: bool, |
f9f354fc | 93 | body: &Body<'tcx>, |
dfeec247 | 94 | move_data: &MoveData<'tcx>, |
b7449926 | 95 | ) -> Self { |
0bf4aa26 | 96 | struct HasStorageDead(BitSet<Local>); |
b7449926 XL |
97 | |
98 | impl<'tcx> Visitor<'tcx> for HasStorageDead { | |
064997fb | 99 | fn visit_local(&mut self, local: Local, ctx: PlaceContext, _: Location) { |
13cf67c4 | 100 | if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) { |
064997fb | 101 | self.0.insert(local); |
b7449926 XL |
102 | } |
103 | } | |
104 | } | |
105 | ||
106 | if locals_are_invalidated_at_exit { | |
107 | LocalsStateAtExit::AllAreInvalidated | |
108 | } else { | |
dfeec247 | 109 | let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len())); |
ba9703b0 | 110 | has_storage_dead.visit_body(&body); |
b7449926 XL |
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); | |
b7449926 XL |
115 | } |
116 | } | |
dfeec247 | 117 | LocalsStateAtExit::SomeAreInvalidated { has_storage_dead_or_moved } |
b7449926 XL |
118 | } |
119 | } | |
120 | } | |
121 | ||
83c7162d | 122 | impl<'tcx> BorrowSet<'tcx> { |
b7449926 | 123 | pub fn build( |
dc9dc135 | 124 | tcx: TyCtxt<'tcx>, |
f9f354fc | 125 | body: &Body<'tcx>, |
b7449926 | 126 | locals_are_invalidated_at_exit: bool, |
dc9dc135 | 127 | move_data: &MoveData<'tcx>, |
b7449926 | 128 | ) -> Self { |
83c7162d XL |
129 | let mut visitor = GatherBorrows { |
130 | tcx, | |
60c5eb7d | 131 | body: &body, |
0bf4aa26 XL |
132 | location_map: Default::default(), |
133 | activation_map: Default::default(), | |
0bf4aa26 XL |
134 | local_map: Default::default(), |
135 | pending_activations: Default::default(), | |
dfeec247 XL |
136 | locals_state_at_exit: LocalsStateAtExit::build( |
137 | locals_are_invalidated_at_exit, | |
138 | body, | |
139 | move_data, | |
140 | ), | |
83c7162d XL |
141 | }; |
142 | ||
60c5eb7d | 143 | for (block, block_data) in traversal::preorder(&body) { |
83c7162d XL |
144 | visitor.visit_basic_block_data(block, block_data); |
145 | } | |
146 | ||
83c7162d | 147 | BorrowSet { |
83c7162d XL |
148 | location_map: visitor.location_map, |
149 | activation_map: visitor.activation_map, | |
83c7162d | 150 | local_map: visitor.local_map, |
b7449926 | 151 | locals_state_at_exit: visitor.locals_state_at_exit, |
83c7162d XL |
152 | } |
153 | } | |
154 | ||
923072b8 | 155 | pub(crate) fn activations_at_location(&self, location: Location) -> &[BorrowIndex] { |
5869c6ff | 156 | self.activation_map.get(&location).map_or(&[], |activations| &activations[..]) |
83c7162d | 157 | } |
3dfed10e | 158 | |
49aad941 | 159 | pub fn len(&self) -> usize { |
3dfed10e XL |
160 | self.location_map.len() |
161 | } | |
162 | ||
923072b8 | 163 | pub(crate) fn indices(&self) -> impl Iterator<Item = BorrowIndex> { |
3dfed10e XL |
164 | BorrowIndex::from_usize(0)..BorrowIndex::from_usize(self.len()) |
165 | } | |
166 | ||
923072b8 | 167 | pub(crate) fn iter_enumerated(&self) -> impl Iterator<Item = (BorrowIndex, &BorrowData<'tcx>)> { |
3dfed10e XL |
168 | self.indices().zip(self.location_map.values()) |
169 | } | |
170 | ||
923072b8 | 171 | pub(crate) fn get_index_of(&self, location: &Location) -> Option<BorrowIndex> { |
3dfed10e XL |
172 | self.location_map.get_index_of(location).map(BorrowIndex::from) |
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>>, |
353b0b11 FG |
180 | activation_map: FxIndexMap<Location, Vec<BorrowIndex>>, |
181 | local_map: FxIndexMap<mir::Local, FxIndexSet<BorrowIndex>>, | |
83c7162d XL |
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). | |
353b0b11 | 191 | pending_activations: FxIndexMap<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 | ) { | |
487cf647 | 203 | if let &mir::Rvalue::Ref(region, kind, 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 | ||
353b0b11 | 209 | let region = region.as_var(); |
a1dfa0c6 | 210 | |
83c7162d XL |
211 | let borrow = BorrowData { |
212 | kind, | |
213 | region, | |
214 | reserve_location: location, | |
8faf50e0 | 215 | activation_location: TwoPhaseActivation::NotTwoPhase, |
487cf647 | 216 | borrowed_place, |
dfeec247 | 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 | ||
064997fb | 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 | |
064997fb | 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) { | |
487cf647 | 278 | if let &mir::Rvalue::Ref(region, kind, place) = rvalue { |
83c7162d XL |
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); | |
353b0b11 | 284 | assert_eq!(borrow_data.region, region.as_var()); |
487cf647 | 285 | assert_eq!(borrow_data.borrowed_place, place); |
83c7162d XL |
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 | } |