1 use crate::borrow_check::borrow_set::BorrowSet;
2 use crate::borrow_check::location::LocationTable;
3 use crate::borrow_check::{JustWrite, WriteAndRead};
4 use crate::borrow_check::{AccessDepth, Deep, Shallow};
5 use crate::borrow_check::{ReadOrWrite, Activation, Read, Reservation, Write};
6 use crate::borrow_check::{LocalMutationIsAllowed, MutateMode};
7 use crate::borrow_check::ArtificialField;
8 use crate::borrow_check::{ReadKind, WriteKind};
9 use crate::borrow_check::nll::facts::AllFacts;
10 use crate::borrow_check::path_utils::*;
11 use crate::dataflow::indexes::BorrowIndex;
12 use rustc::ty::TyCtxt;
13 use rustc::mir::visit::Visitor;
14 use rustc::mir::{BasicBlock, Location, Body, Place, Rvalue};
15 use rustc::mir::{Statement, StatementKind};
16 use rustc::mir::TerminatorKind;
17 use rustc::mir::{Operand, BorrowKind};
18 use rustc_data_structures::graph::dominators::Dominators;
20 pub(super) fn generate_invalidates<'tcx>(
22 all_facts: &mut Option<AllFacts>,
23 location_table: &LocationTable,
25 borrow_set: &BorrowSet<'tcx>,
27 if all_facts.is_none() {
28 // Nothing to do if we don't have any facts
32 if let Some(all_facts) = all_facts {
33 let dominators = body.dominators();
34 let mut ig = InvalidationGenerator {
46 struct InvalidationGenerator<'cx, 'tcx> {
48 all_facts: &'cx mut AllFacts,
49 location_table: &'cx LocationTable,
50 body: &'cx Body<'tcx>,
51 dominators: Dominators<BasicBlock>,
52 borrow_set: &'cx BorrowSet<'tcx>,
55 /// Visits the whole MIR and generates `invalidates()` facts.
56 /// Most of the code implementing this was stolen from `borrow_check/mod.rs`.
57 impl<'cx, 'tcx> Visitor<'tcx> for InvalidationGenerator<'cx, 'tcx> {
60 statement: &Statement<'tcx>,
63 self.check_activations(location);
65 match statement.kind {
66 StatementKind::Assign(ref lhs, ref rhs) => {
79 StatementKind::FakeRead(_, _) => {
80 // Only relavent for initialized/liveness/safety checks.
82 StatementKind::SetDiscriminant {
93 StatementKind::InlineAsm(ref asm) => {
94 for (o, output) in asm.asm.outputs.iter().zip(asm.outputs.iter()) {
96 // FIXME(eddyb) indirect inline asm outputs should
97 // be encoded through MIR place derefs instead.
101 (Deep, Read(ReadKind::Copy)),
102 LocalMutationIsAllowed::No,
108 if o.is_rw { Deep } else { Shallow(None) },
109 if o.is_rw { WriteAndRead } else { JustWrite },
113 for (_, input) in asm.inputs.iter() {
114 self.consume_operand(location, input);
118 StatementKind::AscribeUserType(..) |
119 StatementKind::Retag { .. } |
120 StatementKind::StorageLive(..) => {
121 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
124 StatementKind::StorageDead(local) => {
128 (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
129 LocalMutationIsAllowed::Yes,
134 self.super_statement(statement, location);
137 fn visit_terminator_kind(
139 kind: &TerminatorKind<'tcx>,
142 self.check_activations(location);
145 TerminatorKind::SwitchInt {
151 self.consume_operand(location, discr);
153 TerminatorKind::Drop {
154 location: ref drop_place,
161 (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
162 LocalMutationIsAllowed::Yes,
165 TerminatorKind::DropAndReplace {
166 location: ref drop_place,
167 value: ref new_value,
177 self.consume_operand(
182 TerminatorKind::Call {
189 self.consume_operand(location, func);
191 self.consume_operand(location, arg);
193 if let Some((ref dest, _ /*bb*/)) = *destination {
202 TerminatorKind::Assert {
209 self.consume_operand(location, cond);
210 use rustc::mir::interpret::PanicInfo;
211 if let PanicInfo::BoundsCheck { ref len, ref index } = *msg {
212 self.consume_operand(location, len);
213 self.consume_operand(location, index);
216 TerminatorKind::Yield {
221 self.consume_operand(location, value);
223 // Invalidate all borrows of local places
224 let borrow_set = self.borrow_set.clone();
225 let resume = self.location_table.start_index(resume.start_location());
226 for i in borrow_set.borrows.indices() {
227 if borrow_of_local_data(&borrow_set.borrows[i].borrowed_place) {
228 self.all_facts.invalidates.push((resume, i));
232 TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
233 // Invalidate all borrows of local places
234 let borrow_set = self.borrow_set.clone();
235 let start = self.location_table.start_index(location);
236 for i in borrow_set.borrows.indices() {
237 if borrow_of_local_data(&borrow_set.borrows[i].borrowed_place) {
238 self.all_facts.invalidates.push((start, i));
242 TerminatorKind::Goto { target: _ }
243 | TerminatorKind::Abort
244 | TerminatorKind::Unreachable
245 | TerminatorKind::FalseEdges {
249 | TerminatorKind::FalseUnwind {
253 // no data used, thus irrelevant to borrowck
257 self.super_terminator_kind(kind, location);
261 impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> {
262 /// Simulates mutation of a place.
273 (kind, Write(WriteKind::Mutate)),
274 LocalMutationIsAllowed::ExceptUpvars,
278 /// Simulates consumption of an operand.
282 operand: &Operand<'tcx>,
285 Operand::Copy(ref place) => {
289 (Deep, Read(ReadKind::Copy)),
290 LocalMutationIsAllowed::No,
293 Operand::Move(ref place) => {
297 (Deep, Write(WriteKind::Move)),
298 LocalMutationIsAllowed::Yes,
301 Operand::Constant(_) => {}
305 // Simulates consumption of an rvalue
309 rvalue: &Rvalue<'tcx>,
312 Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
313 let access_kind = match bk {
314 BorrowKind::Shallow => {
315 (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
317 BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
318 BorrowKind::Unique | BorrowKind::Mut { .. } => {
319 let wk = WriteKind::MutableBorrow(bk);
320 if allow_two_phase_borrow(bk) {
321 (Deep, Reservation(wk))
332 LocalMutationIsAllowed::No,
336 Rvalue::Use(ref operand)
337 | Rvalue::Repeat(ref operand, _)
338 | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
339 | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
340 self.consume_operand(location, operand)
343 Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
344 let af = match *rvalue {
345 Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
346 Rvalue::Discriminant(..) => None,
352 (Shallow(af), Read(ReadKind::Copy)),
353 LocalMutationIsAllowed::No,
357 Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
358 | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
359 self.consume_operand(location, operand1);
360 self.consume_operand(location, operand2);
363 Rvalue::NullaryOp(_op, _ty) => {
366 Rvalue::Aggregate(_, ref operands) => {
367 for operand in operands {
368 self.consume_operand(location, operand);
374 /// Simulates an access to a place.
379 kind: (AccessDepth, ReadOrWrite),
380 _is_local_mutation_allowed: LocalMutationIsAllowed,
383 // note: not doing check_access_permissions checks because they don't generate invalidates
384 self.check_access_for_conflict(location, place, sd, rw);
387 fn check_access_for_conflict(
395 "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \
403 let body = self.body;
404 let borrow_set = self.borrow_set.clone();
405 let indices = self.borrow_set.borrows.indices();
406 each_borrow_involving_path(
414 |this, borrow_index, borrow| {
415 match (rw, borrow.kind) {
416 // Obviously an activation is compatible with its own
417 // reservation (or even prior activating uses of same
418 // borrow); so don't check if they interfere.
420 // NOTE: *reservations* do conflict with themselves;
421 // thus aren't injecting unsoundenss w/ this check.)
422 (Activation(_, activating), _) if activating == borrow_index => {
423 // Activating a borrow doesn't generate any invalidations, since we
424 // have already taken the reservation
427 (Read(_), BorrowKind::Shallow)
428 | (Read(_), BorrowKind::Shared)
429 | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Unique)
430 | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Mut { .. }) => {
431 // Reads don't invalidate shared or shallow borrows
434 (Read(_), BorrowKind::Unique) | (Read(_), BorrowKind::Mut { .. }) => {
435 // Reading from mere reservations of mutable-borrows is OK.
436 if !is_active(&this.dominators, borrow, location) {
437 // If the borrow isn't active yet, reads don't invalidate it
438 assert!(allow_two_phase_borrow(borrow.kind));
439 return Control::Continue;
442 // Unique and mutable borrows are invalidated by reads from any
444 this.generate_invalidates(borrow_index, location);
448 | (Activation(_, _), _)
450 // unique or mutable borrows are invalidated by writes.
451 // Reservations count as writes since we need to check
452 // that activating the borrow will be OK
453 // FIXME(bob_twinkles) is this actually the right thing to do?
454 this.generate_invalidates(borrow_index, location);
463 /// Generates a new `invalidates(L, B)` fact.
464 fn generate_invalidates(&mut self, b: BorrowIndex, l: Location) {
465 let lidx = self.location_table.start_index(l);
466 self.all_facts.invalidates.push((lidx, b));
469 fn check_activations(
473 // Two-phase borrow support: For each activation that is newly
474 // generated at this statement, check if it interferes with
476 for &borrow_index in self.borrow_set.activations_at_location(location) {
477 let borrow = &self.borrow_set[borrow_index];
479 // only mutable borrows should be 2-phase
480 assert!(match borrow.kind {
481 BorrowKind::Shared | BorrowKind::Shallow => false,
482 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
487 &borrow.borrowed_place,
490 Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
492 LocalMutationIsAllowed::No,
495 // We do not need to call `check_if_path_or_subpath_is_moved`
496 // again, as we already called it when we made the
497 // initial reservation.