]>
Commit | Line | Data |
---|---|---|
487cf647 FG |
1 | #![deny(rustc::untranslatable_diagnostic)] |
2 | #![deny(rustc::diagnostic_outside_of_impl)] | |
b7449926 | 3 | use rustc_data_structures::fx::FxHashMap; |
dfeec247 | 4 | use rustc_index::bit_set::BitSet; |
c295e0f8 XL |
5 | use rustc_middle::mir::{self, BasicBlock, Body, Location, Place}; |
6 | use rustc_middle::ty::RegionVid; | |
7 | use rustc_middle::ty::TyCtxt; | |
8 | use rustc_mir_dataflow::impls::{EverInitializedPlaces, MaybeUninitializedPlaces}; | |
9 | use rustc_mir_dataflow::ResultsVisitable; | |
a2a8927a | 10 | use rustc_mir_dataflow::{self, fmt::DebugWithContext, CallReturnPlaces, GenKill}; |
c295e0f8 XL |
11 | use rustc_mir_dataflow::{Analysis, Direction, Results}; |
12 | use std::fmt; | |
3b2f2976 | 13 | |
c295e0f8 | 14 | use crate::{ |
74b04a01 | 15 | places_conflict, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, ToRegionVid, |
60c5eb7d | 16 | }; |
3b2f2976 | 17 | |
c295e0f8 XL |
18 | /// A tuple with named fields that can hold either the results or the transient state of the |
19 | /// dataflow analyses used by the borrow checker. | |
20 | #[derive(Debug)] | |
21 | pub struct BorrowckAnalyses<B, U, E> { | |
22 | pub borrows: B, | |
23 | pub uninits: U, | |
24 | pub ever_inits: E, | |
25 | } | |
26 | ||
27 | /// The results of the dataflow analyses used by the borrow checker. | |
28 | pub type BorrowckResults<'mir, 'tcx> = BorrowckAnalyses< | |
29 | Results<'tcx, Borrows<'mir, 'tcx>>, | |
30 | Results<'tcx, MaybeUninitializedPlaces<'mir, 'tcx>>, | |
31 | Results<'tcx, EverInitializedPlaces<'mir, 'tcx>>, | |
32 | >; | |
33 | ||
34 | /// The transient state of the dataflow analyses used by the borrow checker. | |
35 | pub type BorrowckFlowState<'mir, 'tcx> = | |
36 | <BorrowckResults<'mir, 'tcx> as ResultsVisitable<'tcx>>::FlowState; | |
37 | ||
38 | macro_rules! impl_visitable { | |
39 | ( $( | |
40 | $T:ident { $( $field:ident : $A:ident ),* $(,)? } | |
41 | )* ) => { $( | |
42 | impl<'tcx, $($A),*, D: Direction> ResultsVisitable<'tcx> for $T<$( Results<'tcx, $A> ),*> | |
43 | where | |
44 | $( $A: Analysis<'tcx, Direction = D>, )* | |
45 | { | |
46 | type Direction = D; | |
47 | type FlowState = $T<$( $A::Domain ),*>; | |
48 | ||
49 | fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState { | |
50 | $T { | |
51 | $( $field: self.$field.analysis.bottom_value(body) ),* | |
52 | } | |
53 | } | |
54 | ||
55 | fn reset_to_block_entry( | |
56 | &self, | |
57 | state: &mut Self::FlowState, | |
58 | block: BasicBlock, | |
59 | ) { | |
60 | $( state.$field.clone_from(&self.$field.entry_set_for_block(block)); )* | |
61 | } | |
62 | ||
63 | fn reconstruct_before_statement_effect( | |
64 | &self, | |
65 | state: &mut Self::FlowState, | |
66 | stmt: &mir::Statement<'tcx>, | |
67 | loc: Location, | |
68 | ) { | |
69 | $( self.$field.analysis | |
70 | .apply_before_statement_effect(&mut state.$field, stmt, loc); )* | |
71 | } | |
72 | ||
73 | fn reconstruct_statement_effect( | |
74 | &self, | |
75 | state: &mut Self::FlowState, | |
76 | stmt: &mir::Statement<'tcx>, | |
77 | loc: Location, | |
78 | ) { | |
79 | $( self.$field.analysis | |
80 | .apply_statement_effect(&mut state.$field, stmt, loc); )* | |
81 | } | |
82 | ||
83 | fn reconstruct_before_terminator_effect( | |
84 | &self, | |
85 | state: &mut Self::FlowState, | |
86 | term: &mir::Terminator<'tcx>, | |
87 | loc: Location, | |
88 | ) { | |
89 | $( self.$field.analysis | |
90 | .apply_before_terminator_effect(&mut state.$field, term, loc); )* | |
91 | } | |
92 | ||
93 | fn reconstruct_terminator_effect( | |
94 | &self, | |
95 | state: &mut Self::FlowState, | |
96 | term: &mir::Terminator<'tcx>, | |
97 | loc: Location, | |
98 | ) { | |
99 | $( self.$field.analysis | |
100 | .apply_terminator_effect(&mut state.$field, term, loc); )* | |
101 | } | |
102 | } | |
103 | )* } | |
104 | } | |
105 | ||
106 | impl_visitable! { | |
107 | BorrowckAnalyses { borrows: B, uninits: U, ever_inits: E } | |
108 | } | |
3b2f2976 | 109 | |
e74abb32 | 110 | rustc_index::newtype_index! { |
48663c56 XL |
111 | pub struct BorrowIndex { |
112 | DEBUG_FORMAT = "bw{}" | |
113 | } | |
114 | } | |
115 | ||
ff7c6d11 XL |
116 | /// `Borrows` stores the data used in the analyses that track the flow |
117 | /// of borrows. | |
118 | /// | |
119 | /// It uniquely identifies every borrow (`Rvalue::Ref`) by a | |
120 | /// `BorrowIndex`, and maps each such index to a `BorrowData` | |
121 | /// describing the borrow. These indexes are used for representing the | |
122 | /// borrows in compact bitvectors. | |
dc9dc135 XL |
123 | pub struct Borrows<'a, 'tcx> { |
124 | tcx: TyCtxt<'tcx>, | |
125 | body: &'a Body<'tcx>, | |
ff7c6d11 | 126 | |
6a06907d | 127 | borrow_set: &'a BorrowSet<'tcx>, |
94b46f34 | 128 | borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>, |
94b46f34 XL |
129 | } |
130 | ||
b7449926 XL |
131 | struct StackEntry { |
132 | bb: mir::BasicBlock, | |
133 | lo: usize, | |
134 | hi: usize, | |
b7449926 XL |
135 | } |
136 | ||
6a06907d XL |
137 | struct OutOfScopePrecomputer<'a, 'tcx> { |
138 | visited: BitSet<mir::BasicBlock>, | |
139 | visit_stack: Vec<StackEntry>, | |
140 | body: &'a Body<'tcx>, | |
141 | regioncx: &'a RegionInferenceContext<'tcx>, | |
142 | borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>, | |
143 | } | |
144 | ||
145 | impl<'a, 'tcx> OutOfScopePrecomputer<'a, 'tcx> { | |
146 | fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self { | |
147 | OutOfScopePrecomputer { | |
f2b60f7d | 148 | visited: BitSet::new_empty(body.basic_blocks.len()), |
6a06907d XL |
149 | visit_stack: vec![], |
150 | body, | |
151 | regioncx, | |
152 | borrows_out_of_scope_at_location: FxHashMap::default(), | |
94b46f34 | 153 | } |
6a06907d XL |
154 | } |
155 | } | |
94b46f34 | 156 | |
6a06907d XL |
157 | impl<'tcx> OutOfScopePrecomputer<'_, 'tcx> { |
158 | fn precompute_borrows_out_of_scope( | |
159 | &mut self, | |
160 | borrow_index: BorrowIndex, | |
161 | borrow_region: RegionVid, | |
162 | location: Location, | |
163 | ) { | |
164 | // We visit one BB at a time. The complication is that we may start in the | |
165 | // middle of the first BB visited (the one containing `location`), in which | |
166 | // case we may have to later on process the first part of that BB if there | |
167 | // is a path back to its start. | |
168 | ||
169 | // For visited BBs, we record the index of the first statement processed. | |
170 | // (In fully processed BBs this index is 0.) Note also that we add BBs to | |
171 | // `visited` once they are added to `stack`, before they are actually | |
172 | // processed, because this avoids the need to look them up again on | |
173 | // completion. | |
174 | self.visited.insert(location.block); | |
175 | ||
176 | let mut first_lo = location.statement_index; | |
177 | let first_hi = self.body[location.block].statements.len(); | |
178 | ||
179 | self.visit_stack.push(StackEntry { bb: location.block, lo: first_lo, hi: first_hi }); | |
180 | ||
181 | while let Some(StackEntry { bb, lo, hi }) = self.visit_stack.pop() { | |
182 | // If we process the first part of the first basic block (i.e. we encounter that block | |
183 | // for the second time), we no longer have to visit its successors again. | |
184 | let mut finished_early = bb == location.block && hi != first_hi; | |
185 | for i in lo..=hi { | |
186 | let location = Location { block: bb, statement_index: i }; | |
187 | // If region does not contain a point at the location, then add to list and skip | |
188 | // successor locations. | |
189 | if !self.regioncx.region_contains(borrow_region, location) { | |
190 | debug!("borrow {:?} gets killed at {:?}", borrow_index, location); | |
191 | self.borrows_out_of_scope_at_location | |
192 | .entry(location) | |
193 | .or_default() | |
194 | .push(borrow_index); | |
195 | finished_early = true; | |
196 | break; | |
197 | } | |
198 | } | |
199 | ||
200 | if !finished_early { | |
201 | // Add successor BBs to the work list, if necessary. | |
202 | let bb_data = &self.body[bb]; | |
203 | debug_assert!(hi == bb_data.statements.len()); | |
923072b8 | 204 | for succ_bb in bb_data.terminator().successors() { |
c295e0f8 | 205 | if !self.visited.insert(succ_bb) { |
6a06907d XL |
206 | if succ_bb == location.block && first_lo > 0 { |
207 | // `succ_bb` has been seen before. If it wasn't | |
208 | // fully processed, add its first part to `stack` | |
209 | // for processing. | |
210 | self.visit_stack.push(StackEntry { | |
b7449926 XL |
211 | bb: succ_bb, |
212 | lo: 0, | |
6a06907d | 213 | hi: first_lo - 1, |
b7449926 | 214 | }); |
6a06907d XL |
215 | |
216 | // And update this entry with 0, to represent the | |
217 | // whole BB being processed. | |
218 | first_lo = 0; | |
b7449926 | 219 | } |
6a06907d | 220 | } else { |
b7449926 XL |
221 | // succ_bb hasn't been seen before. Add it to |
222 | // `stack` for processing. | |
6a06907d | 223 | self.visit_stack.push(StackEntry { |
b7449926 XL |
224 | bb: succ_bb, |
225 | lo: 0, | |
6a06907d | 226 | hi: self.body[succ_bb].statements.len(), |
b7449926 | 227 | }); |
6a06907d XL |
228 | } |
229 | } | |
94b46f34 XL |
230 | } |
231 | } | |
6a06907d XL |
232 | |
233 | self.visited.clear(); | |
94b46f34 | 234 | } |
3b2f2976 XL |
235 | } |
236 | ||
dc9dc135 | 237 | impl<'a, 'tcx> Borrows<'a, 'tcx> { |
923072b8 | 238 | pub(crate) fn new( |
dc9dc135 XL |
239 | tcx: TyCtxt<'tcx>, |
240 | body: &'a Body<'tcx>, | |
6a06907d XL |
241 | nonlexical_regioncx: &'a RegionInferenceContext<'tcx>, |
242 | borrow_set: &'a BorrowSet<'tcx>, | |
83c7162d | 243 | ) -> Self { |
6a06907d | 244 | let mut prec = OutOfScopePrecomputer::new(body, nonlexical_regioncx); |
3dfed10e | 245 | for (borrow_index, borrow_data) in borrow_set.iter_enumerated() { |
94b46f34 | 246 | let borrow_region = borrow_data.region.to_region_vid(); |
3dfed10e | 247 | let location = borrow_data.reserve_location; |
94b46f34 | 248 | |
6a06907d | 249 | prec.precompute_borrows_out_of_scope(borrow_index, borrow_region, location); |
94b46f34 XL |
250 | } |
251 | ||
83c7162d | 252 | Borrows { |
60c5eb7d XL |
253 | tcx, |
254 | body, | |
6a06907d XL |
255 | borrow_set, |
256 | borrows_out_of_scope_at_location: prec.borrows_out_of_scope_at_location, | |
0531ce1d | 257 | } |
3b2f2976 XL |
258 | } |
259 | ||
3b2f2976 | 260 | pub fn location(&self, idx: BorrowIndex) -> &Location { |
3dfed10e | 261 | &self.borrow_set[idx].reserve_location |
3b2f2976 | 262 | } |
ea8adc8c | 263 | |
abe05a73 | 264 | /// Add all borrows to the kill set, if those borrows are out of scope at `location`. |
a1dfa0c6 | 265 | /// That means they went out of a nonlexical scope |
dfeec247 XL |
266 | fn kill_loans_out_of_scope_at_location( |
267 | &self, | |
74b04a01 | 268 | trans: &mut impl GenKill<BorrowIndex>, |
dfeec247 XL |
269 | location: Location, |
270 | ) { | |
83c7162d | 271 | // NOTE: The state associated with a given `location` |
94b46f34 XL |
272 | // reflects the dataflow on entry to the statement. |
273 | // Iterate over each of the borrows that we've precomputed | |
274 | // to have went out of scope at this location and kill them. | |
83c7162d XL |
275 | // |
276 | // We are careful always to call this function *before* we | |
277 | // set up the gen-bits for the statement or | |
29967ef6 | 278 | // terminator. That way, if the effect of the statement or |
83c7162d XL |
279 | // terminator *does* introduce a new loan of the same |
280 | // region, then setting that gen-bit will override any | |
281 | // potential kill introduced here. | |
94b46f34 | 282 | if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) { |
74b04a01 | 283 | trans.kill_all(indices.iter().copied()); |
abe05a73 | 284 | } |
ea8adc8c | 285 | } |
3b2f2976 | 286 | |
0731742a | 287 | /// Kill any borrows that conflict with `place`. |
ba9703b0 | 288 | fn kill_borrows_on_place(&self, trans: &mut impl GenKill<BorrowIndex>, place: Place<'tcx>) { |
0731742a | 289 | debug!("kill_borrows_on_place: place={:?}", place); |
dc9dc135 | 290 | |
74b04a01 XL |
291 | let other_borrows_of_local = self |
292 | .borrow_set | |
293 | .local_map | |
294 | .get(&place.local) | |
295 | .into_iter() | |
296 | .flat_map(|bs| bs.iter()) | |
297 | .copied(); | |
dfeec247 XL |
298 | |
299 | // If the borrowed place is a local with no projections, all other borrows of this | |
300 | // local must conflict. This is purely an optimization so we don't have to call | |
301 | // `places_conflict` for every borrow. | |
302 | if place.projection.is_empty() { | |
303 | if !self.body.local_decls[place.local].is_ref_to_static() { | |
304 | trans.kill_all(other_borrows_of_local); | |
0731742a | 305 | } |
dfeec247 XL |
306 | return; |
307 | } | |
0731742a | 308 | |
dfeec247 XL |
309 | // By passing `PlaceConflictBias::NoOverlap`, we conservatively assume that any given |
310 | // pair of array indices are unequal, so that when `places_conflict` returns true, we | |
311 | // will be assured that two places being compared definitely denotes the same sets of | |
312 | // locations. | |
74b04a01 | 313 | let definitely_conflicting_borrows = other_borrows_of_local.filter(|&i| { |
dfeec247 XL |
314 | places_conflict( |
315 | self.tcx, | |
316 | self.body, | |
3dfed10e | 317 | self.borrow_set[i].borrowed_place, |
dfeec247 XL |
318 | place, |
319 | PlaceConflictBias::NoOverlap, | |
320 | ) | |
321 | }); | |
dc9dc135 | 322 | |
dfeec247 | 323 | trans.kill_all(definitely_conflicting_borrows); |
0531ce1d XL |
324 | } |
325 | } | |
326 | ||
c295e0f8 | 327 | impl<'tcx> rustc_mir_dataflow::AnalysisDomain<'tcx> for Borrows<'_, 'tcx> { |
1b1a35ee | 328 | type Domain = BitSet<BorrowIndex>; |
74b04a01 XL |
329 | |
330 | const NAME: &'static str = "borrows"; | |
331 | ||
1b1a35ee XL |
332 | fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain { |
333 | // bottom = nothing is reserved or activated yet; | |
334 | BitSet::new_empty(self.borrow_set.len() * 2) | |
0531ce1d XL |
335 | } |
336 | ||
1b1a35ee | 337 | fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) { |
0531ce1d | 338 | // no borrows of code region_scopes have been taken prior to |
dc9dc135 | 339 | // function execution, so this method has no effect. |
0531ce1d | 340 | } |
74b04a01 | 341 | } |
0531ce1d | 342 | |
c295e0f8 | 343 | impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { |
1b1a35ee XL |
344 | type Idx = BorrowIndex; |
345 | ||
74b04a01 XL |
346 | fn before_statement_effect( |
347 | &self, | |
348 | trans: &mut impl GenKill<Self::Idx>, | |
349 | _statement: &mir::Statement<'tcx>, | |
350 | location: Location, | |
351 | ) { | |
352 | self.kill_loans_out_of_scope_at_location(trans, location); | |
353 | } | |
ff7c6d11 | 354 | |
74b04a01 XL |
355 | fn statement_effect( |
356 | &self, | |
357 | trans: &mut impl GenKill<Self::Idx>, | |
358 | stmt: &mir::Statement<'tcx>, | |
359 | location: Location, | |
360 | ) { | |
487cf647 FG |
361 | match &stmt.kind { |
362 | mir::StatementKind::Assign(box (lhs, rhs)) => { | |
363 | if let mir::Rvalue::Ref(_, _, place) = rhs { | |
b7449926 XL |
364 | if place.ignore_borrow( |
365 | self.tcx, | |
dc9dc135 | 366 | self.body, |
b7449926 XL |
367 | &self.borrow_set.locals_state_at_exit, |
368 | ) { | |
369 | return; | |
370 | } | |
3dfed10e | 371 | let index = self.borrow_set.get_index_of(&location).unwrap_or_else(|| { |
0531ce1d XL |
372 | panic!("could not find BorrowIndex for location {:?}", location); |
373 | }); | |
374 | ||
3dfed10e | 375 | trans.gen(index); |
ff7c6d11 | 376 | } |
e1599b0c XL |
377 | |
378 | // Make sure there are no remaining borrows for variables | |
379 | // that are assigned over. | |
487cf647 | 380 | self.kill_borrows_on_place(trans, *lhs); |
ff7c6d11 XL |
381 | } |
382 | ||
383 | mir::StatementKind::StorageDead(local) => { | |
384 | // Make sure there are no remaining borrows for locals that | |
385 | // are gone out of scope. | |
487cf647 | 386 | self.kill_borrows_on_place(trans, Place::from(*local)); |
ff7c6d11 XL |
387 | } |
388 | ||
dfeec247 XL |
389 | mir::StatementKind::FakeRead(..) |
390 | | mir::StatementKind::SetDiscriminant { .. } | |
04454e1e | 391 | | mir::StatementKind::Deinit(..) |
dfeec247 XL |
392 | | mir::StatementKind::StorageLive(..) |
393 | | mir::StatementKind::Retag { .. } | |
394 | | mir::StatementKind::AscribeUserType(..) | |
3dfed10e | 395 | | mir::StatementKind::Coverage(..) |
f2b60f7d | 396 | | mir::StatementKind::Intrinsic(..) |
dfeec247 | 397 | | mir::StatementKind::Nop => {} |
3b2f2976 | 398 | } |
ff7c6d11 | 399 | } |
abe05a73 | 400 | |
74b04a01 XL |
401 | fn before_terminator_effect( |
402 | &self, | |
403 | trans: &mut impl GenKill<Self::Idx>, | |
404 | _terminator: &mir::Terminator<'tcx>, | |
405 | location: Location, | |
406 | ) { | |
dc9dc135 | 407 | self.kill_loans_out_of_scope_at_location(trans, location); |
ff7c6d11 XL |
408 | } |
409 | ||
74b04a01 XL |
410 | fn terminator_effect( |
411 | &self, | |
f9f354fc | 412 | trans: &mut impl GenKill<Self::Idx>, |
5e7ed085 | 413 | terminator: &mir::Terminator<'tcx>, |
f9f354fc | 414 | _location: Location, |
74b04a01 | 415 | ) { |
5e7ed085 | 416 | if let mir::TerminatorKind::InlineAsm { operands, .. } = &terminator.kind { |
f9f354fc XL |
417 | for op in operands { |
418 | if let mir::InlineAsmOperand::Out { place: Some(place), .. } | |
419 | | mir::InlineAsmOperand::InOut { out_place: Some(place), .. } = *op | |
420 | { | |
421 | self.kill_borrows_on_place(trans, place); | |
422 | } | |
423 | } | |
424 | } | |
74b04a01 | 425 | } |
ff7c6d11 | 426 | |
74b04a01 | 427 | fn call_return_effect( |
0731742a | 428 | &self, |
74b04a01 XL |
429 | _trans: &mut impl GenKill<Self::Idx>, |
430 | _block: mir::BasicBlock, | |
a2a8927a | 431 | _return_places: CallReturnPlaces<'_, 'tcx>, |
0731742a | 432 | ) { |
ff7c6d11 XL |
433 | } |
434 | } | |
435 | ||
1b1a35ee XL |
436 | impl DebugWithContext<Borrows<'_, '_>> for BorrowIndex { |
437 | fn fmt_with(&self, ctxt: &Borrows<'_, '_>, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
438 | write!(f, "{:?}", ctxt.location(*self)) | |
439 | } | |
3b2f2976 | 440 | } |