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::{Context, ContextKind};
7 use crate::borrow_check::{LocalMutationIsAllowed, MutateMode};
8 use crate::borrow_check::ArtificialField;
9 use crate::borrow_check::{ReadKind, WriteKind};
10 use crate::borrow_check::nll::facts::AllFacts;
11 use crate::borrow_check::path_utils::*;
12 use crate::dataflow::indexes::BorrowIndex;
13 use rustc::ty::TyCtxt;
14 use rustc::mir::visit::Visitor;
15 use rustc::mir::{BasicBlock, Location, Mir, Place, PlaceBase, Rvalue};
16 use rustc::mir::{Statement, StatementKind};
17 use rustc::mir::TerminatorKind;
18 use rustc::mir::{Operand, BorrowKind};
19 use rustc_data_structures::graph::dominators::Dominators;
21 pub(super) fn generate_invalidates<'cx, 'gcx, 'tcx>(
22 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
23 all_facts: &mut Option<AllFacts>,
24 location_table: &LocationTable,
26 borrow_set: &BorrowSet<'tcx>,
28 if all_facts.is_none() {
29 // Nothing to do if we don't have any facts
33 if let Some(all_facts) = all_facts {
34 let dominators = mir.dominators();
35 let mut ig = InvalidationGenerator {
47 struct InvalidationGenerator<'cx, 'tcx: 'cx, 'gcx: 'tcx> {
48 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
49 all_facts: &'cx mut AllFacts,
50 location_table: &'cx LocationTable,
52 dominators: Dominators<BasicBlock>,
53 borrow_set: &'cx BorrowSet<'tcx>,
56 /// Visits the whole MIR and generates `invalidates()` facts.
57 /// Most of the code implementing this was stolen from `borrow_check/mod.rs`.
58 impl<'cx, 'tcx, 'gcx> Visitor<'tcx> for InvalidationGenerator<'cx, 'tcx, 'gcx> {
61 statement: &Statement<'tcx>,
64 self.check_activations(location);
66 match statement.kind {
67 StatementKind::Assign(ref lhs, ref rhs) => {
69 ContextKind::AssignRhs.new(location),
74 ContextKind::AssignLhs.new(location),
80 StatementKind::FakeRead(_, _) => {
81 // Only relavent for initialized/liveness/safety checks.
83 StatementKind::SetDiscriminant {
88 ContextKind::SetDiscrim.new(location),
94 StatementKind::InlineAsm(ref asm) => {
95 let context = ContextKind::InlineAsm.new(location);
96 for (o, output) in asm.asm.outputs.iter().zip(asm.outputs.iter()) {
98 // FIXME(eddyb) indirect inline asm outputs should
99 // be encoded through MIR place derefs instead.
103 (Deep, Read(ReadKind::Copy)),
104 LocalMutationIsAllowed::No,
110 if o.is_rw { Deep } else { Shallow(None) },
111 if o.is_rw { WriteAndRead } else { JustWrite },
115 for (_, input) in asm.inputs.iter() {
116 self.consume_operand(context, input);
120 StatementKind::AscribeUserType(..) |
121 StatementKind::Retag { .. } |
122 StatementKind::StorageLive(..) => {
123 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
126 StatementKind::StorageDead(local) => {
128 ContextKind::StorageDead.new(location),
129 &Place::Base(PlaceBase::Local(local)),
130 (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
131 LocalMutationIsAllowed::Yes,
136 self.super_statement(statement, location);
139 fn visit_terminator_kind(
141 kind: &TerminatorKind<'tcx>,
144 self.check_activations(location);
147 TerminatorKind::SwitchInt {
153 self.consume_operand(ContextKind::SwitchInt.new(location), discr);
155 TerminatorKind::Drop {
156 location: ref drop_place,
161 ContextKind::Drop.new(location),
163 (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
164 LocalMutationIsAllowed::Yes,
167 TerminatorKind::DropAndReplace {
168 location: ref drop_place,
169 value: ref new_value,
174 ContextKind::DropAndReplace.new(location),
179 self.consume_operand(
180 ContextKind::DropAndReplace.new(location),
184 TerminatorKind::Call {
191 self.consume_operand(ContextKind::CallOperator.new(location), func);
193 self.consume_operand(ContextKind::CallOperand.new(location), arg);
195 if let Some((ref dest, _ /*bb*/)) = *destination {
197 ContextKind::CallDest.new(location),
204 TerminatorKind::Assert {
211 self.consume_operand(ContextKind::Assert.new(location), cond);
212 use rustc::mir::interpret::InterpError::BoundsCheck;
213 if let BoundsCheck { ref len, ref index } = *msg {
214 self.consume_operand(ContextKind::Assert.new(location), len);
215 self.consume_operand(ContextKind::Assert.new(location), index);
218 TerminatorKind::Yield {
223 self.consume_operand(ContextKind::Yield.new(location), value);
225 // Invalidate all borrows of local places
226 let borrow_set = self.borrow_set.clone();
227 let resume = self.location_table.start_index(resume.start_location());
228 for i in borrow_set.borrows.indices() {
229 if borrow_of_local_data(&borrow_set.borrows[i].borrowed_place) {
230 self.all_facts.invalidates.push((resume, i));
234 TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
235 // Invalidate all borrows of local places
236 let borrow_set = self.borrow_set.clone();
237 let start = self.location_table.start_index(location);
238 for i in borrow_set.borrows.indices() {
239 if borrow_of_local_data(&borrow_set.borrows[i].borrowed_place) {
240 self.all_facts.invalidates.push((start, i));
244 TerminatorKind::Goto { target: _ }
245 | TerminatorKind::Abort
246 | TerminatorKind::Unreachable
247 | TerminatorKind::FalseEdges {
249 imaginary_targets: _,
251 | TerminatorKind::FalseUnwind {
255 // no data used, thus irrelevant to borrowck
259 self.super_terminator_kind(kind, location);
263 impl<'cg, 'cx, 'tcx, 'gcx> InvalidationGenerator<'cx, 'tcx, 'gcx> {
264 /// Simulates mutation of a place.
275 (kind, Write(WriteKind::Mutate)),
276 LocalMutationIsAllowed::ExceptUpvars,
280 /// Simulates consumption of an operand.
284 operand: &Operand<'tcx>,
287 Operand::Copy(ref place) => {
291 (Deep, Read(ReadKind::Copy)),
292 LocalMutationIsAllowed::No,
295 Operand::Move(ref place) => {
299 (Deep, Write(WriteKind::Move)),
300 LocalMutationIsAllowed::Yes,
303 Operand::Constant(_) => {}
307 // Simulates consumption of an rvalue
311 rvalue: &Rvalue<'tcx>,
314 Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
315 let access_kind = match bk {
316 BorrowKind::Shallow => {
317 (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
319 BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
320 BorrowKind::Unique | BorrowKind::Mut { .. } => {
321 let wk = WriteKind::MutableBorrow(bk);
322 if allow_two_phase_borrow(&self.tcx, bk) {
323 (Deep, Reservation(wk))
334 LocalMutationIsAllowed::No,
338 Rvalue::Use(ref operand)
339 | Rvalue::Repeat(ref operand, _)
340 | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
341 | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
342 self.consume_operand(context, operand)
345 Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
346 let af = match *rvalue {
347 Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
348 Rvalue::Discriminant(..) => None,
354 (Shallow(af), Read(ReadKind::Copy)),
355 LocalMutationIsAllowed::No,
359 Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
360 | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
361 self.consume_operand(context, operand1);
362 self.consume_operand(context, operand2);
365 Rvalue::NullaryOp(_op, _ty) => {
368 Rvalue::Aggregate(_, ref operands) => {
369 for operand in operands {
370 self.consume_operand(context, operand);
376 /// Simulates an access to a place.
381 kind: (AccessDepth, ReadOrWrite),
382 _is_local_mutation_allowed: LocalMutationIsAllowed,
385 // note: not doing check_access_permissions checks because they don't generate invalidates
386 self.check_access_for_conflict(context, place, sd, rw);
389 fn check_access_for_conflict(
397 "invalidation::check_access_for_conflict(context={:?}, place={:?}, sd={:?}, \
406 let borrow_set = self.borrow_set.clone();
407 let indices = self.borrow_set.borrows.indices();
408 each_borrow_involving_path(
416 |this, borrow_index, borrow| {
417 match (rw, borrow.kind) {
418 // Obviously an activation is compatible with its own
419 // reservation (or even prior activating uses of same
420 // borrow); so don't check if they interfere.
422 // NOTE: *reservations* do conflict with themselves;
423 // thus aren't injecting unsoundenss w/ this check.)
424 (Activation(_, activating), _) if activating == borrow_index => {
425 // Activating a borrow doesn't generate any invalidations, since we
426 // have already taken the reservation
429 (Read(_), BorrowKind::Shallow)
430 | (Read(_), BorrowKind::Shared)
431 | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Unique)
432 | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Mut { .. }) => {
433 // Reads don't invalidate shared or shallow borrows
436 (Read(_), BorrowKind::Unique) | (Read(_), BorrowKind::Mut { .. }) => {
437 // Reading from mere reservations of mutable-borrows is OK.
438 if !is_active(&this.dominators, borrow, context.loc) {
439 // If the borrow isn't active yet, reads don't invalidate it
440 assert!(allow_two_phase_borrow(&this.tcx, borrow.kind));
441 return Control::Continue;
444 // Unique and mutable borrows are invalidated by reads from any
446 this.generate_invalidates(borrow_index, context.loc);
450 | (Activation(_, _), _)
452 // unique or mutable borrows are invalidated by writes.
453 // Reservations count as writes since we need to check
454 // that activating the borrow will be OK
455 // FIXME(bob_twinkles) is this actually the right thing to do?
456 this.generate_invalidates(borrow_index, context.loc);
465 /// Generates a new `invalidates(L, B)` fact.
466 fn generate_invalidates(&mut self, b: BorrowIndex, l: Location) {
467 let lidx = self.location_table.start_index(l);
468 self.all_facts.invalidates.push((lidx, b));
471 fn check_activations(
475 // Two-phase borrow support: For each activation that is newly
476 // generated at this statement, check if it interferes with
478 for &borrow_index in self.borrow_set.activations_at_location(location) {
479 let borrow = &self.borrow_set[borrow_index];
481 // only mutable borrows should be 2-phase
482 assert!(match borrow.kind {
483 BorrowKind::Shared | BorrowKind::Shallow => false,
484 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
488 ContextKind::Activation.new(location),
489 &borrow.borrowed_place,
492 Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
494 LocalMutationIsAllowed::No,
497 // We do not need to call `check_if_path_or_subpath_is_moved`
498 // again, as we already called it when we made the
499 // initial reservation.