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;
9 use crate::dataflow::indexes::BorrowIndex;
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,
17 pub(super) fn generate_invalidates<'tcx>(
19 all_facts: &mut Option<AllFacts>,
20 location_table: &LocationTable,
22 borrow_set: &BorrowSet<'tcx>,
24 if all_facts.is_none() {
25 // Nothing to do if we don't have any facts
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 {
44 struct InvalidationGenerator<'cx, '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>,
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);
59 match &statement.kind {
60 StatementKind::Assign(box (lhs, rhs)) => {
61 self.consume_rvalue(location, rhs);
63 self.mutate_place(location, *lhs, Shallow(None), JustWrite);
65 StatementKind::FakeRead(_, _) => {
66 // Only relevant for initialized/liveness/safety checks.
68 StatementKind::SetDiscriminant { place, variant_index: _ } => {
69 self.mutate_place(location, **place, Shallow(None), JustWrite);
71 StatementKind::LlvmInlineAsm(asm) => {
72 for (o, output) in asm.asm.outputs.iter().zip(asm.outputs.iter()) {
74 // FIXME(eddyb) indirect inline asm outputs should
75 // be encoded through MIR place derefs instead.
79 (Deep, Read(ReadKind::Copy)),
80 LocalMutationIsAllowed::No,
86 if o.is_rw { Deep } else { Shallow(None) },
87 if o.is_rw { WriteAndRead } else { JustWrite },
91 for (_, input) in asm.inputs.iter() {
92 self.consume_operand(location, input);
96 | StatementKind::AscribeUserType(..)
97 | StatementKind::Retag { .. }
98 | StatementKind::StorageLive(..) => {
99 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
102 StatementKind::StorageDead(local) => {
106 (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
107 LocalMutationIsAllowed::Yes,
112 self.super_statement(statement, location);
115 fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
116 self.check_activations(location);
118 match &terminator.kind {
119 TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => {
120 self.consume_operand(location, discr);
122 TerminatorKind::Drop { place: drop_place, target: _, unwind: _ } => {
126 (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
127 LocalMutationIsAllowed::Yes,
130 TerminatorKind::DropAndReplace {
132 value: ref new_value,
136 self.mutate_place(location, *drop_place, Deep, JustWrite);
137 self.consume_operand(location, new_value);
139 TerminatorKind::Call {
147 self.consume_operand(location, func);
149 self.consume_operand(location, arg);
151 if let Some((dest, _ /*bb*/)) = destination {
152 self.mutate_place(location, *dest, Deep, JustWrite);
155 TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
156 self.consume_operand(location, cond);
157 use rustc_middle::mir::AssertKind;
158 if let AssertKind::BoundsCheck { ref len, ref index } = *msg {
159 self.consume_operand(location, len);
160 self.consume_operand(location, index);
163 TerminatorKind::Yield { ref value, resume, resume_arg, drop: _ } => {
164 self.consume_operand(location, value);
166 // Invalidate all borrows of local places
167 let borrow_set = self.borrow_set.clone();
168 let resume = self.location_table.start_index(resume.start_location());
169 for i in borrow_set.borrows.indices() {
170 if borrow_of_local_data(borrow_set.borrows[i].borrowed_place) {
171 self.all_facts.invalidates.push((resume, i));
175 self.mutate_place(location, *resume_arg, Deep, JustWrite);
177 TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
178 // Invalidate all borrows of local places
179 let borrow_set = self.borrow_set.clone();
180 let start = self.location_table.start_index(location);
181 for i in borrow_set.borrows.indices() {
182 if borrow_of_local_data(borrow_set.borrows[i].borrowed_place) {
183 self.all_facts.invalidates.push((start, i));
187 TerminatorKind::InlineAsm {
196 InlineAsmOperand::In { reg: _, ref value }
197 | InlineAsmOperand::Const { ref value } => {
198 self.consume_operand(location, value);
200 InlineAsmOperand::Out { reg: _, late: _, place, .. } => {
201 if let Some(place) = place {
202 self.mutate_place(location, place, Shallow(None), JustWrite);
205 InlineAsmOperand::InOut { reg: _, late: _, ref in_value, out_place } => {
206 self.consume_operand(location, in_value);
207 if let Some(out_place) = out_place {
208 self.mutate_place(location, out_place, Shallow(None), JustWrite);
211 InlineAsmOperand::SymFn { value: _ }
212 | InlineAsmOperand::SymStatic { def_id: _ } => {}
216 TerminatorKind::Goto { target: _ }
217 | TerminatorKind::Abort
218 | TerminatorKind::Unreachable
219 | TerminatorKind::FalseEdge { real_target: _, imaginary_target: _ }
220 | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
221 // no data used, thus irrelevant to borrowck
225 self.super_terminator(terminator, location);
229 impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> {
230 /// Simulates mutation of a place.
241 (kind, Write(WriteKind::Mutate)),
242 LocalMutationIsAllowed::ExceptUpvars,
246 /// Simulates consumption of an operand.
247 fn consume_operand(&mut self, location: Location, operand: &Operand<'tcx>) {
249 Operand::Copy(place) => {
253 (Deep, Read(ReadKind::Copy)),
254 LocalMutationIsAllowed::No,
257 Operand::Move(place) => {
261 (Deep, Write(WriteKind::Move)),
262 LocalMutationIsAllowed::Yes,
265 Operand::Constant(_) => {}
269 // Simulates consumption of an rvalue
270 fn consume_rvalue(&mut self, location: Location, rvalue: &Rvalue<'tcx>) {
272 Rvalue::Ref(_ /*rgn*/, bk, place) => {
273 let access_kind = match bk {
274 BorrowKind::Shallow => {
275 (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
277 BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
278 BorrowKind::Unique | BorrowKind::Mut { .. } => {
279 let wk = WriteKind::MutableBorrow(bk);
280 if allow_two_phase_borrow(bk) {
281 (Deep, Reservation(wk))
288 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
291 Rvalue::AddressOf(mutability, place) => {
292 let access_kind = match mutability {
295 Write(WriteKind::MutableBorrow(BorrowKind::Mut {
296 allow_two_phase_borrow: false,
299 Mutability::Not => (Deep, Read(ReadKind::Borrow(BorrowKind::Shared))),
302 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
305 Rvalue::ThreadLocalRef(_) => {}
307 Rvalue::Use(ref operand)
308 | Rvalue::Repeat(ref operand, _)
309 | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
310 | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
311 self.consume_operand(location, operand)
314 Rvalue::Len(place) | Rvalue::Discriminant(place) => {
315 let af = match *rvalue {
316 Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
317 Rvalue::Discriminant(..) => None,
323 (Shallow(af), Read(ReadKind::Copy)),
324 LocalMutationIsAllowed::No,
328 Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
329 | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
330 self.consume_operand(location, operand1);
331 self.consume_operand(location, operand2);
334 Rvalue::NullaryOp(_op, _ty) => {}
336 Rvalue::Aggregate(_, ref operands) => {
337 for operand in operands {
338 self.consume_operand(location, operand);
344 /// Simulates an access to a place.
349 kind: (AccessDepth, ReadOrWrite),
350 _is_local_mutation_allowed: LocalMutationIsAllowed,
353 // note: not doing check_access_permissions checks because they don't generate invalidates
354 self.check_access_for_conflict(location, place, sd, rw);
357 fn check_access_for_conflict(
365 "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \
367 location, place, sd, rw,
370 let body = self.body;
371 let borrow_set = self.borrow_set.clone();
372 let indices = self.borrow_set.borrows.indices();
373 each_borrow_involving_path(
381 |this, borrow_index, borrow| {
382 match (rw, borrow.kind) {
383 // Obviously an activation is compatible with its own
384 // reservation (or even prior activating uses of same
385 // borrow); so don't check if they interfere.
387 // NOTE: *reservations* do conflict with themselves;
388 // thus aren't injecting unsoundenss w/ this check.)
389 (Activation(_, activating), _) if activating == borrow_index => {
390 // Activating a borrow doesn't generate any invalidations, since we
391 // have already taken the reservation
394 (Read(_), BorrowKind::Shallow | BorrowKind::Shared)
396 Read(ReadKind::Borrow(BorrowKind::Shallow)),
397 BorrowKind::Unique | BorrowKind::Mut { .. },
399 // Reads don't invalidate shared or shallow borrows
402 (Read(_), BorrowKind::Unique | BorrowKind::Mut { .. }) => {
403 // Reading from mere reservations of mutable-borrows is OK.
404 if !is_active(&this.dominators, borrow, location) {
405 // If the borrow isn't active yet, reads don't invalidate it
406 assert!(allow_two_phase_borrow(borrow.kind));
407 return Control::Continue;
410 // Unique and mutable borrows are invalidated by reads from any
412 this.generate_invalidates(borrow_index, location);
415 (Reservation(_) | Activation(_, _) | Write(_), _) => {
416 // unique or mutable borrows are invalidated by writes.
417 // Reservations count as writes since we need to check
418 // that activating the borrow will be OK
419 // FIXME(bob_twinkles) is this actually the right thing to do?
420 this.generate_invalidates(borrow_index, location);
428 /// Generates a new `invalidates(L, B)` fact.
429 fn generate_invalidates(&mut self, b: BorrowIndex, l: Location) {
430 let lidx = self.location_table.start_index(l);
431 self.all_facts.invalidates.push((lidx, b));
434 fn check_activations(&mut self, location: Location) {
435 // Two-phase borrow support: For each activation that is newly
436 // generated at this statement, check if it interferes with
438 for &borrow_index in self.borrow_set.activations_at_location(location) {
439 let borrow = &self.borrow_set[borrow_index];
441 // only mutable borrows should be 2-phase
442 assert!(match borrow.kind {
443 BorrowKind::Shared | BorrowKind::Shallow => false,
444 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
449 borrow.borrowed_place,
450 (Deep, Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index)),
451 LocalMutationIsAllowed::No,
454 // We do not need to call `check_if_path_or_subpath_is_moved`
455 // again, as we already called it when we made the
456 // initial reservation.