]>
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 | |
923072b8 | 33 | pub(crate) 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 ", |
83c7162d XL |
75 | mir::BorrowKind::Unique => "uniq ", |
76 | mir::BorrowKind::Mut { .. } => "mut ", | |
77 | }; | |
a1dfa0c6 | 78 | write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place) |
83c7162d XL |
79 | } |
80 | } | |
81 | ||
3c0e092e | 82 | pub enum LocalsStateAtExit { |
b7449926 | 83 | AllAreInvalidated, |
dfeec247 | 84 | SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }, |
b7449926 XL |
85 | } |
86 | ||
87 | impl LocalsStateAtExit { | |
a2a8927a | 88 | fn build<'tcx>( |
b7449926 | 89 | locals_are_invalidated_at_exit: bool, |
f9f354fc | 90 | body: &Body<'tcx>, |
dfeec247 | 91 | move_data: &MoveData<'tcx>, |
b7449926 | 92 | ) -> Self { |
0bf4aa26 | 93 | struct HasStorageDead(BitSet<Local>); |
b7449926 XL |
94 | |
95 | impl<'tcx> Visitor<'tcx> for HasStorageDead { | |
064997fb | 96 | fn visit_local(&mut self, local: Local, ctx: PlaceContext, _: Location) { |
13cf67c4 | 97 | if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) { |
064997fb | 98 | self.0.insert(local); |
b7449926 XL |
99 | } |
100 | } | |
101 | } | |
102 | ||
103 | if locals_are_invalidated_at_exit { | |
104 | LocalsStateAtExit::AllAreInvalidated | |
105 | } else { | |
dfeec247 | 106 | let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len())); |
ba9703b0 | 107 | has_storage_dead.visit_body(&body); |
b7449926 XL |
108 | let mut has_storage_dead_or_moved = has_storage_dead.0; |
109 | for move_out in &move_data.moves { | |
110 | if let Some(index) = move_data.base_local(move_out.path) { | |
111 | has_storage_dead_or_moved.insert(index); | |
b7449926 XL |
112 | } |
113 | } | |
dfeec247 | 114 | LocalsStateAtExit::SomeAreInvalidated { has_storage_dead_or_moved } |
b7449926 XL |
115 | } |
116 | } | |
117 | } | |
118 | ||
83c7162d | 119 | impl<'tcx> BorrowSet<'tcx> { |
b7449926 | 120 | pub fn build( |
dc9dc135 | 121 | tcx: TyCtxt<'tcx>, |
f9f354fc | 122 | body: &Body<'tcx>, |
b7449926 | 123 | locals_are_invalidated_at_exit: bool, |
dc9dc135 | 124 | move_data: &MoveData<'tcx>, |
b7449926 | 125 | ) -> Self { |
83c7162d XL |
126 | let mut visitor = GatherBorrows { |
127 | tcx, | |
60c5eb7d | 128 | body: &body, |
0bf4aa26 XL |
129 | location_map: Default::default(), |
130 | activation_map: Default::default(), | |
0bf4aa26 XL |
131 | local_map: Default::default(), |
132 | pending_activations: Default::default(), | |
dfeec247 XL |
133 | locals_state_at_exit: LocalsStateAtExit::build( |
134 | locals_are_invalidated_at_exit, | |
135 | body, | |
136 | move_data, | |
137 | ), | |
83c7162d XL |
138 | }; |
139 | ||
60c5eb7d | 140 | for (block, block_data) in traversal::preorder(&body) { |
83c7162d XL |
141 | visitor.visit_basic_block_data(block, block_data); |
142 | } | |
143 | ||
83c7162d | 144 | BorrowSet { |
83c7162d XL |
145 | location_map: visitor.location_map, |
146 | activation_map: visitor.activation_map, | |
83c7162d | 147 | local_map: visitor.local_map, |
b7449926 | 148 | locals_state_at_exit: visitor.locals_state_at_exit, |
83c7162d XL |
149 | } |
150 | } | |
151 | ||
923072b8 | 152 | pub(crate) fn activations_at_location(&self, location: Location) -> &[BorrowIndex] { |
5869c6ff | 153 | self.activation_map.get(&location).map_or(&[], |activations| &activations[..]) |
83c7162d | 154 | } |
3dfed10e | 155 | |
923072b8 | 156 | pub(crate) fn len(&self) -> usize { |
3dfed10e XL |
157 | self.location_map.len() |
158 | } | |
159 | ||
923072b8 | 160 | pub(crate) fn indices(&self) -> impl Iterator<Item = BorrowIndex> { |
3dfed10e XL |
161 | BorrowIndex::from_usize(0)..BorrowIndex::from_usize(self.len()) |
162 | } | |
163 | ||
923072b8 | 164 | pub(crate) fn iter_enumerated(&self) -> impl Iterator<Item = (BorrowIndex, &BorrowData<'tcx>)> { |
3dfed10e XL |
165 | self.indices().zip(self.location_map.values()) |
166 | } | |
167 | ||
923072b8 | 168 | pub(crate) fn get_index_of(&self, location: &Location) -> Option<BorrowIndex> { |
3dfed10e XL |
169 | self.location_map.get_index_of(location).map(BorrowIndex::from) |
170 | } | |
83c7162d XL |
171 | } |
172 | ||
dc9dc135 XL |
173 | struct GatherBorrows<'a, 'tcx> { |
174 | tcx: TyCtxt<'tcx>, | |
175 | body: &'a Body<'tcx>, | |
3dfed10e | 176 | location_map: FxIndexMap<Location, BorrowData<'tcx>>, |
353b0b11 FG |
177 | activation_map: FxIndexMap<Location, Vec<BorrowIndex>>, |
178 | local_map: FxIndexMap<mir::Local, FxIndexSet<BorrowIndex>>, | |
83c7162d XL |
179 | |
180 | /// When we encounter a 2-phase borrow statement, it will always | |
181 | /// be assigning into a temporary TEMP: | |
182 | /// | |
183 | /// TEMP = &foo | |
184 | /// | |
185 | /// We add TEMP into this map with `b`, where `b` is the index of | |
186 | /// the borrow. When we find a later use of this activation, we | |
187 | /// remove from the map (and add to the "tombstone" set below). | |
353b0b11 | 188 | pending_activations: FxIndexMap<mir::Local, BorrowIndex>, |
b7449926 XL |
189 | |
190 | locals_state_at_exit: LocalsStateAtExit, | |
83c7162d XL |
191 | } |
192 | ||
dc9dc135 | 193 | impl<'a, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'tcx> { |
83c7162d XL |
194 | fn visit_assign( |
195 | &mut self, | |
83c7162d XL |
196 | assigned_place: &mir::Place<'tcx>, |
197 | rvalue: &mir::Rvalue<'tcx>, | |
198 | location: mir::Location, | |
199 | ) { | |
487cf647 | 200 | if let &mir::Rvalue::Ref(region, kind, borrowed_place) = rvalue { |
60c5eb7d XL |
201 | if borrowed_place.ignore_borrow(self.tcx, self.body, &self.locals_state_at_exit) { |
202 | debug!("ignoring_borrow of {:?}", borrowed_place); | |
83c7162d XL |
203 | return; |
204 | } | |
205 | ||
353b0b11 | 206 | let region = region.as_var(); |
a1dfa0c6 | 207 | |
83c7162d XL |
208 | let borrow = BorrowData { |
209 | kind, | |
210 | region, | |
211 | reserve_location: location, | |
8faf50e0 | 212 | activation_location: TwoPhaseActivation::NotTwoPhase, |
487cf647 | 213 | borrowed_place, |
dfeec247 | 214 | assigned_place: *assigned_place, |
83c7162d | 215 | }; |
3dfed10e XL |
216 | let (idx, _) = self.location_map.insert_full(location, borrow); |
217 | let idx = BorrowIndex::from(idx); | |
83c7162d | 218 | |
ba9703b0 | 219 | self.insert_as_pending_if_two_phase(location, assigned_place, kind, idx); |
83c7162d | 220 | |
dfeec247 | 221 | self.local_map.entry(borrowed_place.local).or_default().insert(idx); |
83c7162d XL |
222 | } |
223 | ||
48663c56 | 224 | self.super_assign(assigned_place, rvalue, location) |
83c7162d XL |
225 | } |
226 | ||
064997fb | 227 | fn visit_local(&mut self, temp: Local, context: PlaceContext, location: Location) { |
0731742a XL |
228 | if !context.is_use() { |
229 | return; | |
230 | } | |
83c7162d | 231 | |
0731742a XL |
232 | // We found a use of some temporary TMP |
233 | // check whether we (earlier) saw a 2-phase borrow like | |
234 | // | |
235 | // TMP = &mut place | |
064997fb | 236 | if let Some(&borrow_index) = self.pending_activations.get(&temp) { |
3dfed10e | 237 | let borrow_data = &mut self.location_map[borrow_index.as_usize()]; |
0731742a XL |
238 | |
239 | // Watch out: the use of TMP in the borrow itself | |
240 | // doesn't count as an activation. =) | |
dfeec247 XL |
241 | if borrow_data.reserve_location == location |
242 | && context == PlaceContext::MutatingUse(MutatingUseContext::Store) | |
0731742a XL |
243 | { |
244 | return; | |
245 | } | |
83c7162d | 246 | |
dfeec247 XL |
247 | if let TwoPhaseActivation::ActivatedAt(other_location) = borrow_data.activation_location |
248 | { | |
0731742a | 249 | span_bug!( |
dc9dc135 | 250 | self.body.source_info(location).span, |
0731742a XL |
251 | "found two uses for 2-phase borrow temporary {:?}: \ |
252 | {:?} and {:?}", | |
253 | temp, | |
254 | location, | |
255 | other_location, | |
256 | ); | |
83c7162d | 257 | } |
0731742a | 258 | |
9fa01778 XL |
259 | // Otherwise, this is the unique later use that we expect. |
260 | // Double check: This borrow is indeed a two-phase borrow (that is, | |
261 | // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and | |
262 | // we've not found any other activations (checked above). | |
263 | assert_eq!( | |
264 | borrow_data.activation_location, | |
265 | TwoPhaseActivation::NotActivated, | |
266 | "never found an activation for this borrow!", | |
267 | ); | |
dfeec247 | 268 | self.activation_map.entry(location).or_default().push(borrow_index); |
9fa01778 XL |
269 | |
270 | borrow_data.activation_location = TwoPhaseActivation::ActivatedAt(location); | |
83c7162d XL |
271 | } |
272 | } | |
273 | ||
274 | fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location) { | |
487cf647 | 275 | if let &mir::Rvalue::Ref(region, kind, place) = rvalue { |
83c7162d XL |
276 | // double-check that we already registered a BorrowData for this |
277 | ||
3dfed10e | 278 | let borrow_data = &self.location_map[&location]; |
83c7162d XL |
279 | assert_eq!(borrow_data.reserve_location, location); |
280 | assert_eq!(borrow_data.kind, kind); | |
353b0b11 | 281 | assert_eq!(borrow_data.region, region.as_var()); |
487cf647 | 282 | assert_eq!(borrow_data.borrowed_place, place); |
83c7162d XL |
283 | } |
284 | ||
ba9703b0 | 285 | self.super_rvalue(rvalue, location) |
83c7162d | 286 | } |
83c7162d XL |
287 | } |
288 | ||
dc9dc135 | 289 | impl<'a, 'tcx> GatherBorrows<'a, 'tcx> { |
83c7162d XL |
290 | /// If this is a two-phase borrow, then we will record it |
291 | /// as "pending" until we find the activating use. | |
292 | fn insert_as_pending_if_two_phase( | |
293 | &mut self, | |
294 | start_location: Location, | |
295 | assigned_place: &mir::Place<'tcx>, | |
83c7162d XL |
296 | kind: mir::BorrowKind, |
297 | borrow_index: BorrowIndex, | |
298 | ) { | |
299 | debug!( | |
a1dfa0c6 XL |
300 | "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})", |
301 | start_location, assigned_place, borrow_index, | |
83c7162d XL |
302 | ); |
303 | ||
48663c56 | 304 | if !allow_two_phase_borrow(kind) { |
83c7162d XL |
305 | debug!(" -> {:?}", start_location); |
306 | return; | |
307 | } | |
308 | ||
309 | // When we encounter a 2-phase borrow statement, it will always | |
310 | // be assigning into a temporary TEMP: | |
311 | // | |
312 | // TEMP = &foo | |
313 | // | |
314 | // so extract `temp`. | |
3c0e092e | 315 | let Some(temp) = assigned_place.as_local() else { |
83c7162d | 316 | span_bug!( |
dc9dc135 | 317 | self.body.source_info(start_location).span, |
83c7162d XL |
318 | "expected 2-phase borrow to assign to a local, not `{:?}`", |
319 | assigned_place, | |
320 | ); | |
321 | }; | |
322 | ||
8faf50e0 XL |
323 | // Consider the borrow not activated to start. When we find an activation, we'll update |
324 | // this field. | |
325 | { | |
3dfed10e | 326 | let borrow_data = &mut self.location_map[borrow_index.as_usize()]; |
8faf50e0 XL |
327 | borrow_data.activation_location = TwoPhaseActivation::NotActivated; |
328 | } | |
329 | ||
83c7162d XL |
330 | // Insert `temp` into the list of pending activations. From |
331 | // now on, we'll be on the lookout for a use of it. Note that | |
332 | // we are guaranteed that this use will come after the | |
333 | // assignment. | |
334 | let old_value = self.pending_activations.insert(temp, borrow_index); | |
8faf50e0 | 335 | if let Some(old_index) = old_value { |
dfeec247 XL |
336 | span_bug!( |
337 | self.body.source_info(start_location).span, | |
338 | "found already pending activation for temp: {:?} \ | |
8faf50e0 | 339 | at borrow_index: {:?} with associated data {:?}", |
dfeec247 XL |
340 | temp, |
341 | old_index, | |
3dfed10e | 342 | self.location_map[old_index.as_usize()] |
dfeec247 | 343 | ); |
8faf50e0 | 344 | } |
83c7162d XL |
345 | } |
346 | } |