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