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