1 use rustc_data_structures::graph::dominators::Dominators;
2 use rustc_middle::mir::visit::Visitor;
3 use rustc_middle::mir::{self, BasicBlock, Body, Location, NonDivergingIntrinsic, 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;
10 borrow_set::BorrowSet, facts::AllFacts, location::LocationTable, path_utils::*, AccessDepth,
11 Activation, ArtificialField, BorrowIndex, Deep, LocalMutationIsAllowed, Read, ReadKind,
12 ReadOrWrite, Reservation, Shallow, Write, WriteKind,
15 pub(super) fn generate_invalidates<'tcx>(
17 all_facts: &mut Option<AllFacts>,
18 location_table: &LocationTable,
20 borrow_set: &BorrowSet<'tcx>,
22 if all_facts.is_none() {
23 // Nothing to do if we don't have any facts
27 if let Some(all_facts) = all_facts {
28 let _prof_timer = tcx.prof.generic_activity("polonius_fact_generation");
29 let dominators = body.basic_blocks.dominators();
30 let mut ig = InvalidationGenerator {
42 struct InvalidationGenerator<'cx, 'tcx> {
44 all_facts: &'cx mut AllFacts,
45 location_table: &'cx LocationTable,
46 body: &'cx Body<'tcx>,
47 dominators: Dominators<BasicBlock>,
48 borrow_set: &'cx BorrowSet<'tcx>,
51 /// Visits the whole MIR and generates `invalidates()` facts.
52 /// Most of the code implementing this was stolen from `borrow_check/mod.rs`.
53 impl<'cx, 'tcx> Visitor<'tcx> for InvalidationGenerator<'cx, 'tcx> {
54 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
55 self.check_activations(location);
57 match &statement.kind {
58 StatementKind::Assign(box (lhs, rhs)) => {
59 self.consume_rvalue(location, rhs);
61 self.mutate_place(location, *lhs, Shallow(None));
63 StatementKind::FakeRead(box (_, _)) => {
64 // Only relevant for initialized/liveness/safety checks.
66 StatementKind::Intrinsic(box NonDivergingIntrinsic::Assume(op)) => {
67 self.consume_operand(location, op);
69 StatementKind::Intrinsic(box NonDivergingIntrinsic::CopyNonOverlapping(mir::CopyNonOverlapping {
74 self.consume_operand(location, src);
75 self.consume_operand(location, dst);
76 self.consume_operand(location, count);
78 // Only relevant for mir typeck
79 StatementKind::AscribeUserType(..)
80 // Doesn't have any language semantics
81 | StatementKind::Coverage(..)
82 // Does not actually affect borrowck
83 | StatementKind::StorageLive(..) => {}
84 StatementKind::StorageDead(local) => {
88 (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
89 LocalMutationIsAllowed::Yes,
93 | StatementKind::Retag { .. }
94 | StatementKind::Deinit(..)
95 | StatementKind::SetDiscriminant { .. } => {
96 bug!("Statement not allowed in this MIR phase")
100 self.super_statement(statement, location);
103 fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
104 self.check_activations(location);
106 match &terminator.kind {
107 TerminatorKind::SwitchInt { ref discr, switch_ty: _, targets: _ } => {
108 self.consume_operand(location, discr);
110 TerminatorKind::Drop { place: drop_place, target: _, unwind: _ } => {
114 (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
115 LocalMutationIsAllowed::Yes,
118 TerminatorKind::DropAndReplace {
120 value: ref new_value,
124 self.mutate_place(location, *drop_place, Deep);
125 self.consume_operand(location, new_value);
127 TerminatorKind::Call {
136 self.consume_operand(location, func);
138 self.consume_operand(location, arg);
140 self.mutate_place(location, *destination, Deep);
142 TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
143 self.consume_operand(location, cond);
144 use rustc_middle::mir::AssertKind;
145 if let AssertKind::BoundsCheck { ref len, ref index } = *msg {
146 self.consume_operand(location, len);
147 self.consume_operand(location, index);
150 TerminatorKind::Yield { ref value, resume, resume_arg, drop: _ } => {
151 self.consume_operand(location, value);
153 // Invalidate all borrows of local places
154 let borrow_set = self.borrow_set;
155 let resume = self.location_table.start_index(resume.start_location());
156 for (i, data) in borrow_set.iter_enumerated() {
157 if borrow_of_local_data(data.borrowed_place) {
158 self.all_facts.loan_invalidated_at.push((resume, i));
162 self.mutate_place(location, *resume_arg, Deep);
164 TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
165 // Invalidate all borrows of local places
166 let borrow_set = self.borrow_set;
167 let start = self.location_table.start_index(location);
168 for (i, data) in borrow_set.iter_enumerated() {
169 if borrow_of_local_data(data.borrowed_place) {
170 self.all_facts.loan_invalidated_at.push((start, i));
174 TerminatorKind::InlineAsm {
184 InlineAsmOperand::In { reg: _, ref value } => {
185 self.consume_operand(location, value);
187 InlineAsmOperand::Out { reg: _, late: _, place, .. } => {
188 if let Some(place) = place {
189 self.mutate_place(location, place, Shallow(None));
192 InlineAsmOperand::InOut { reg: _, late: _, ref in_value, out_place } => {
193 self.consume_operand(location, in_value);
194 if let Some(out_place) = out_place {
195 self.mutate_place(location, out_place, Shallow(None));
198 InlineAsmOperand::Const { value: _ }
199 | InlineAsmOperand::SymFn { value: _ }
200 | InlineAsmOperand::SymStatic { def_id: _ } => {}
204 TerminatorKind::Goto { target: _ }
205 | TerminatorKind::Abort
206 | TerminatorKind::Unreachable
207 | TerminatorKind::FalseEdge { real_target: _, imaginary_target: _ }
208 | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
209 // no data used, thus irrelevant to borrowck
213 self.super_terminator(terminator, location);
217 impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> {
218 /// Simulates mutation of a place.
219 fn mutate_place(&mut self, location: Location, place: Place<'tcx>, kind: AccessDepth) {
223 (kind, Write(WriteKind::Mutate)),
224 LocalMutationIsAllowed::ExceptUpvars,
228 /// Simulates consumption of an operand.
229 fn consume_operand(&mut self, location: Location, operand: &Operand<'tcx>) {
231 Operand::Copy(place) => {
235 (Deep, Read(ReadKind::Copy)),
236 LocalMutationIsAllowed::No,
239 Operand::Move(place) => {
243 (Deep, Write(WriteKind::Move)),
244 LocalMutationIsAllowed::Yes,
247 Operand::Constant(_) => {}
251 // Simulates consumption of an rvalue
252 fn consume_rvalue(&mut self, location: Location, rvalue: &Rvalue<'tcx>) {
254 Rvalue::Ref(_ /*rgn*/, bk, place) => {
255 let access_kind = match bk {
256 BorrowKind::Shallow => {
257 (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
259 BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
260 BorrowKind::Unique | BorrowKind::Mut { .. } => {
261 let wk = WriteKind::MutableBorrow(bk);
262 if allow_two_phase_borrow(bk) {
263 (Deep, Reservation(wk))
270 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
273 Rvalue::AddressOf(mutability, place) => {
274 let access_kind = match mutability {
277 Write(WriteKind::MutableBorrow(BorrowKind::Mut {
278 allow_two_phase_borrow: false,
281 Mutability::Not => (Deep, Read(ReadKind::Borrow(BorrowKind::Shared))),
284 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
287 Rvalue::ThreadLocalRef(_) => {}
289 Rvalue::Use(ref operand)
290 | Rvalue::Repeat(ref operand, _)
291 | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
292 | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/)
293 | Rvalue::ShallowInitBox(ref operand, _ /*ty*/) => {
294 self.consume_operand(location, operand)
296 Rvalue::CopyForDeref(ref place) => {
297 let op = &Operand::Copy(*place);
298 self.consume_operand(location, op);
301 Rvalue::Len(place) | Rvalue::Discriminant(place) => {
302 let af = match *rvalue {
303 Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
304 Rvalue::Discriminant(..) => None,
310 (Shallow(af), Read(ReadKind::Copy)),
311 LocalMutationIsAllowed::No,
315 Rvalue::BinaryOp(_bin_op, box (ref operand1, ref operand2))
316 | Rvalue::CheckedBinaryOp(_bin_op, box (ref operand1, ref operand2)) => {
317 self.consume_operand(location, operand1);
318 self.consume_operand(location, operand2);
321 Rvalue::NullaryOp(_op, _ty) => {}
323 Rvalue::Aggregate(_, ref operands) => {
324 for operand in operands {
325 self.consume_operand(location, operand);
331 /// Simulates an access to a place.
336 kind: (AccessDepth, ReadOrWrite),
337 _is_local_mutation_allowed: LocalMutationIsAllowed,
340 // note: not doing check_access_permissions checks because they don't generate invalidates
341 self.check_access_for_conflict(location, place, sd, rw);
344 fn check_access_for_conflict(
352 "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \
354 location, place, sd, rw,
357 let body = self.body;
358 let borrow_set = self.borrow_set;
359 let indices = self.borrow_set.indices();
360 each_borrow_involving_path(
368 |this, borrow_index, borrow| {
369 match (rw, borrow.kind) {
370 // Obviously an activation is compatible with its own
371 // reservation (or even prior activating uses of same
372 // borrow); so don't check if they interfere.
374 // NOTE: *reservations* do conflict with themselves;
375 // thus aren't injecting unsoundness w/ this check.)
376 (Activation(_, activating), _) if activating == borrow_index => {
377 // Activating a borrow doesn't generate any invalidations, since we
378 // have already taken the reservation
381 (Read(_), BorrowKind::Shallow | BorrowKind::Shared)
383 Read(ReadKind::Borrow(BorrowKind::Shallow)),
384 BorrowKind::Unique | BorrowKind::Mut { .. },
386 // Reads don't invalidate shared or shallow borrows
389 (Read(_), BorrowKind::Unique | BorrowKind::Mut { .. }) => {
390 // Reading from mere reservations of mutable-borrows is OK.
391 if !is_active(&this.dominators, borrow, location) {
392 // If the borrow isn't active yet, reads don't invalidate it
393 assert!(allow_two_phase_borrow(borrow.kind));
394 return Control::Continue;
397 // Unique and mutable borrows are invalidated by reads from any
399 this.emit_loan_invalidated_at(borrow_index, location);
402 (Reservation(_) | Activation(_, _) | Write(_), _) => {
403 // unique or mutable borrows are invalidated by writes.
404 // Reservations count as writes since we need to check
405 // that activating the borrow will be OK
406 // FIXME(bob_twinkles) is this actually the right thing to do?
407 this.emit_loan_invalidated_at(borrow_index, location);
415 /// Generates a new `loan_invalidated_at(L, B)` fact.
416 fn emit_loan_invalidated_at(&mut self, b: BorrowIndex, l: Location) {
417 let lidx = self.location_table.start_index(l);
418 self.all_facts.loan_invalidated_at.push((lidx, b));
421 fn check_activations(&mut self, location: Location) {
422 // Two-phase borrow support: For each activation that is newly
423 // generated at this statement, check if it interferes with
425 for &borrow_index in self.borrow_set.activations_at_location(location) {
426 let borrow = &self.borrow_set[borrow_index];
428 // only mutable borrows should be 2-phase
429 assert!(match borrow.kind {
430 BorrowKind::Shared | BorrowKind::Shallow => false,
431 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
436 borrow.borrowed_place,
437 (Deep, Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index)),
438 LocalMutationIsAllowed::No,
441 // We do not need to call `check_if_path_or_subpath_is_moved`
442 // again, as we already called it when we made the
443 // initial reservation.