]> git.proxmox.com Git - rustc.git/blob - src/librustc_mir/borrow_check/invalidation.rs
New upstream version 1.47.0+dfsg1
[rustc.git] / src / librustc_mir / borrow_check / invalidation.rs
1 use rustc_data_structures::graph::dominators::Dominators;
2 use rustc_middle::mir::visit::Visitor;
3 use rustc_middle::mir::{BasicBlock, Body, Location, Place, Rvalue};
4 use rustc_middle::mir::{BorrowKind, Mutability, Operand};
5 use rustc_middle::mir::{InlineAsmOperand, Terminator, TerminatorKind};
6 use rustc_middle::mir::{Statement, StatementKind};
7 use rustc_middle::ty::TyCtxt;
8
9 use crate::dataflow::indexes::BorrowIndex;
10
11 use crate::borrow_check::{
12 borrow_set::BorrowSet, facts::AllFacts, location::LocationTable, path_utils::*, AccessDepth,
13 Activation, ArtificialField, Deep, JustWrite, LocalMutationIsAllowed, MutateMode, Read,
14 ReadKind, ReadOrWrite, Reservation, Shallow, Write, WriteAndRead, WriteKind,
15 };
16
17 pub(super) fn generate_invalidates<'tcx>(
18 tcx: TyCtxt<'tcx>,
19 all_facts: &mut Option<AllFacts>,
20 location_table: &LocationTable,
21 body: &Body<'tcx>,
22 borrow_set: &BorrowSet<'tcx>,
23 ) {
24 if all_facts.is_none() {
25 // Nothing to do if we don't have any facts
26 return;
27 }
28
29 if let Some(all_facts) = all_facts {
30 let _prof_timer = tcx.prof.generic_activity("polonius_fact_generation");
31 let dominators = body.dominators();
32 let mut ig = InvalidationGenerator {
33 all_facts,
34 borrow_set,
35 tcx,
36 location_table,
37 body: &body,
38 dominators,
39 };
40 ig.visit_body(body);
41 }
42 }
43
44 struct InvalidationGenerator<'cx, 'tcx> {
45 tcx: TyCtxt<'tcx>,
46 all_facts: &'cx mut AllFacts,
47 location_table: &'cx LocationTable,
48 body: &'cx Body<'tcx>,
49 dominators: Dominators<BasicBlock>,
50 borrow_set: &'cx BorrowSet<'tcx>,
51 }
52
53 /// Visits the whole MIR and generates `invalidates()` facts.
54 /// Most of the code implementing this was stolen from `borrow_check/mod.rs`.
55 impl<'cx, 'tcx> Visitor<'tcx> for InvalidationGenerator<'cx, 'tcx> {
56 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
57 self.check_activations(location);
58
59 match &statement.kind {
60 StatementKind::Assign(box (lhs, rhs)) => {
61 self.consume_rvalue(location, rhs);
62
63 self.mutate_place(location, *lhs, Shallow(None), JustWrite);
64 }
65 StatementKind::FakeRead(_, _) => {
66 // Only relevant for initialized/liveness/safety checks.
67 }
68 StatementKind::SetDiscriminant { place, variant_index: _ } => {
69 self.mutate_place(location, **place, Shallow(None), JustWrite);
70 }
71 StatementKind::LlvmInlineAsm(asm) => {
72 for (o, output) in asm.asm.outputs.iter().zip(asm.outputs.iter()) {
73 if o.is_indirect {
74 // FIXME(eddyb) indirect inline asm outputs should
75 // be encoded through MIR place derefs instead.
76 self.access_place(
77 location,
78 *output,
79 (Deep, Read(ReadKind::Copy)),
80 LocalMutationIsAllowed::No,
81 );
82 } else {
83 self.mutate_place(
84 location,
85 *output,
86 if o.is_rw { Deep } else { Shallow(None) },
87 if o.is_rw { WriteAndRead } else { JustWrite },
88 );
89 }
90 }
91 for (_, input) in asm.inputs.iter() {
92 self.consume_operand(location, input);
93 }
94 }
95 StatementKind::Nop
96 | StatementKind::Coverage(..)
97 | StatementKind::AscribeUserType(..)
98 | StatementKind::Retag { .. }
99 | StatementKind::StorageLive(..) => {
100 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
101 // to borrow check.
102 }
103 StatementKind::StorageDead(local) => {
104 self.access_place(
105 location,
106 Place::from(*local),
107 (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
108 LocalMutationIsAllowed::Yes,
109 );
110 }
111 }
112
113 self.super_statement(statement, location);
114 }
115
116 fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
117 self.check_activations(location);
118
119 match &terminator.kind {
120 TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => {
121 self.consume_operand(location, discr);
122 }
123 TerminatorKind::Drop { place: drop_place, target: _, unwind: _ } => {
124 self.access_place(
125 location,
126 *drop_place,
127 (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
128 LocalMutationIsAllowed::Yes,
129 );
130 }
131 TerminatorKind::DropAndReplace {
132 place: drop_place,
133 value: ref new_value,
134 target: _,
135 unwind: _,
136 } => {
137 self.mutate_place(location, *drop_place, Deep, JustWrite);
138 self.consume_operand(location, new_value);
139 }
140 TerminatorKind::Call {
141 ref func,
142 ref args,
143 destination,
144 cleanup: _,
145 from_hir_call: _,
146 fn_span: _,
147 } => {
148 self.consume_operand(location, func);
149 for arg in args {
150 self.consume_operand(location, arg);
151 }
152 if let Some((dest, _ /*bb*/)) = destination {
153 self.mutate_place(location, *dest, Deep, JustWrite);
154 }
155 }
156 TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
157 self.consume_operand(location, cond);
158 use rustc_middle::mir::AssertKind;
159 if let AssertKind::BoundsCheck { ref len, ref index } = *msg {
160 self.consume_operand(location, len);
161 self.consume_operand(location, index);
162 }
163 }
164 TerminatorKind::Yield { ref value, resume, resume_arg, drop: _ } => {
165 self.consume_operand(location, value);
166
167 // Invalidate all borrows of local places
168 let borrow_set = self.borrow_set.clone();
169 let resume = self.location_table.start_index(resume.start_location());
170 for (i, data) in borrow_set.iter_enumerated() {
171 if borrow_of_local_data(data.borrowed_place) {
172 self.all_facts.invalidates.push((resume, i));
173 }
174 }
175
176 self.mutate_place(location, *resume_arg, Deep, JustWrite);
177 }
178 TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
179 // Invalidate all borrows of local places
180 let borrow_set = self.borrow_set.clone();
181 let start = self.location_table.start_index(location);
182 for (i, data) in borrow_set.iter_enumerated() {
183 if borrow_of_local_data(data.borrowed_place) {
184 self.all_facts.invalidates.push((start, i));
185 }
186 }
187 }
188 TerminatorKind::InlineAsm {
189 template: _,
190 ref operands,
191 options: _,
192 line_spans: _,
193 destination: _,
194 } => {
195 for op in operands {
196 match *op {
197 InlineAsmOperand::In { reg: _, ref value }
198 | InlineAsmOperand::Const { ref value } => {
199 self.consume_operand(location, value);
200 }
201 InlineAsmOperand::Out { reg: _, late: _, place, .. } => {
202 if let Some(place) = place {
203 self.mutate_place(location, place, Shallow(None), JustWrite);
204 }
205 }
206 InlineAsmOperand::InOut { reg: _, late: _, ref in_value, out_place } => {
207 self.consume_operand(location, in_value);
208 if let Some(out_place) = out_place {
209 self.mutate_place(location, out_place, Shallow(None), JustWrite);
210 }
211 }
212 InlineAsmOperand::SymFn { value: _ }
213 | InlineAsmOperand::SymStatic { def_id: _ } => {}
214 }
215 }
216 }
217 TerminatorKind::Goto { target: _ }
218 | TerminatorKind::Abort
219 | TerminatorKind::Unreachable
220 | TerminatorKind::FalseEdge { real_target: _, imaginary_target: _ }
221 | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
222 // no data used, thus irrelevant to borrowck
223 }
224 }
225
226 self.super_terminator(terminator, location);
227 }
228 }
229
230 impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> {
231 /// Simulates mutation of a place.
232 fn mutate_place(
233 &mut self,
234 location: Location,
235 place: Place<'tcx>,
236 kind: AccessDepth,
237 _mode: MutateMode,
238 ) {
239 self.access_place(
240 location,
241 place,
242 (kind, Write(WriteKind::Mutate)),
243 LocalMutationIsAllowed::ExceptUpvars,
244 );
245 }
246
247 /// Simulates consumption of an operand.
248 fn consume_operand(&mut self, location: Location, operand: &Operand<'tcx>) {
249 match *operand {
250 Operand::Copy(place) => {
251 self.access_place(
252 location,
253 place,
254 (Deep, Read(ReadKind::Copy)),
255 LocalMutationIsAllowed::No,
256 );
257 }
258 Operand::Move(place) => {
259 self.access_place(
260 location,
261 place,
262 (Deep, Write(WriteKind::Move)),
263 LocalMutationIsAllowed::Yes,
264 );
265 }
266 Operand::Constant(_) => {}
267 }
268 }
269
270 // Simulates consumption of an rvalue
271 fn consume_rvalue(&mut self, location: Location, rvalue: &Rvalue<'tcx>) {
272 match *rvalue {
273 Rvalue::Ref(_ /*rgn*/, bk, place) => {
274 let access_kind = match bk {
275 BorrowKind::Shallow => {
276 (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
277 }
278 BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
279 BorrowKind::Unique | BorrowKind::Mut { .. } => {
280 let wk = WriteKind::MutableBorrow(bk);
281 if allow_two_phase_borrow(bk) {
282 (Deep, Reservation(wk))
283 } else {
284 (Deep, Write(wk))
285 }
286 }
287 };
288
289 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
290 }
291
292 Rvalue::AddressOf(mutability, place) => {
293 let access_kind = match mutability {
294 Mutability::Mut => (
295 Deep,
296 Write(WriteKind::MutableBorrow(BorrowKind::Mut {
297 allow_two_phase_borrow: false,
298 })),
299 ),
300 Mutability::Not => (Deep, Read(ReadKind::Borrow(BorrowKind::Shared))),
301 };
302
303 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
304 }
305
306 Rvalue::ThreadLocalRef(_) => {}
307
308 Rvalue::Use(ref operand)
309 | Rvalue::Repeat(ref operand, _)
310 | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
311 | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
312 self.consume_operand(location, operand)
313 }
314
315 Rvalue::Len(place) | Rvalue::Discriminant(place) => {
316 let af = match *rvalue {
317 Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
318 Rvalue::Discriminant(..) => None,
319 _ => unreachable!(),
320 };
321 self.access_place(
322 location,
323 place,
324 (Shallow(af), Read(ReadKind::Copy)),
325 LocalMutationIsAllowed::No,
326 );
327 }
328
329 Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
330 | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
331 self.consume_operand(location, operand1);
332 self.consume_operand(location, operand2);
333 }
334
335 Rvalue::NullaryOp(_op, _ty) => {}
336
337 Rvalue::Aggregate(_, ref operands) => {
338 for operand in operands {
339 self.consume_operand(location, operand);
340 }
341 }
342 }
343 }
344
345 /// Simulates an access to a place.
346 fn access_place(
347 &mut self,
348 location: Location,
349 place: Place<'tcx>,
350 kind: (AccessDepth, ReadOrWrite),
351 _is_local_mutation_allowed: LocalMutationIsAllowed,
352 ) {
353 let (sd, rw) = kind;
354 // note: not doing check_access_permissions checks because they don't generate invalidates
355 self.check_access_for_conflict(location, place, sd, rw);
356 }
357
358 fn check_access_for_conflict(
359 &mut self,
360 location: Location,
361 place: Place<'tcx>,
362 sd: AccessDepth,
363 rw: ReadOrWrite,
364 ) {
365 debug!(
366 "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \
367 rw={:?})",
368 location, place, sd, rw,
369 );
370 let tcx = self.tcx;
371 let body = self.body;
372 let borrow_set = self.borrow_set.clone();
373 let indices = self.borrow_set.indices();
374 each_borrow_involving_path(
375 self,
376 tcx,
377 body,
378 location,
379 (sd, place),
380 &borrow_set.clone(),
381 indices,
382 |this, borrow_index, borrow| {
383 match (rw, borrow.kind) {
384 // Obviously an activation is compatible with its own
385 // reservation (or even prior activating uses of same
386 // borrow); so don't check if they interfere.
387 //
388 // NOTE: *reservations* do conflict with themselves;
389 // thus aren't injecting unsoundenss w/ this check.)
390 (Activation(_, activating), _) if activating == borrow_index => {
391 // Activating a borrow doesn't generate any invalidations, since we
392 // have already taken the reservation
393 }
394
395 (Read(_), BorrowKind::Shallow | BorrowKind::Shared)
396 | (
397 Read(ReadKind::Borrow(BorrowKind::Shallow)),
398 BorrowKind::Unique | BorrowKind::Mut { .. },
399 ) => {
400 // Reads don't invalidate shared or shallow borrows
401 }
402
403 (Read(_), BorrowKind::Unique | BorrowKind::Mut { .. }) => {
404 // Reading from mere reservations of mutable-borrows is OK.
405 if !is_active(&this.dominators, borrow, location) {
406 // If the borrow isn't active yet, reads don't invalidate it
407 assert!(allow_two_phase_borrow(borrow.kind));
408 return Control::Continue;
409 }
410
411 // Unique and mutable borrows are invalidated by reads from any
412 // involved path
413 this.generate_invalidates(borrow_index, location);
414 }
415
416 (Reservation(_) | Activation(_, _) | Write(_), _) => {
417 // unique or mutable borrows are invalidated by writes.
418 // Reservations count as writes since we need to check
419 // that activating the borrow will be OK
420 // FIXME(bob_twinkles) is this actually the right thing to do?
421 this.generate_invalidates(borrow_index, location);
422 }
423 }
424 Control::Continue
425 },
426 );
427 }
428
429 /// Generates a new `invalidates(L, B)` fact.
430 fn generate_invalidates(&mut self, b: BorrowIndex, l: Location) {
431 let lidx = self.location_table.start_index(l);
432 self.all_facts.invalidates.push((lidx, b));
433 }
434
435 fn check_activations(&mut self, location: Location) {
436 // Two-phase borrow support: For each activation that is newly
437 // generated at this statement, check if it interferes with
438 // another borrow.
439 for &borrow_index in self.borrow_set.activations_at_location(location) {
440 let borrow = &self.borrow_set[borrow_index];
441
442 // only mutable borrows should be 2-phase
443 assert!(match borrow.kind {
444 BorrowKind::Shared | BorrowKind::Shallow => false,
445 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
446 });
447
448 self.access_place(
449 location,
450 borrow.borrowed_place,
451 (Deep, Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index)),
452 LocalMutationIsAllowed::No,
453 );
454
455 // We do not need to call `check_if_path_or_subpath_is_moved`
456 // again, as we already called it when we made the
457 // initial reservation.
458 }
459 }
460 }