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