src/librustc_mir/borrow_check/invalidation.rs

   1 use rustc::mir::visit::Visitor;
   2 use rustc::mir::TerminatorKind;
   3 use rustc::mir::{BasicBlock, Body, Location, Place, ReadOnlyBodyAndCache, Rvalue};
   4 use rustc::mir::{BorrowKind, Mutability, Operand};
   5 use rustc::mir::{Statement, StatementKind};
   6 use rustc::ty::TyCtxt;
   7 use rustc_data_structures::graph::dominators::Dominators;
   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: ReadOnlyBodyAndCache<'_, '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 (ref lhs, ref rhs)) => {
  61                 self.consume_rvalue(location, rhs);
  62
  63                 self.mutate_place(location, lhs, Shallow(None), JustWrite);
  64             }
  65             StatementKind::FakeRead(_, _) => {
  66                 // Only relavent for initialized/liveness/safety checks.
  67             }
  68             StatementKind::SetDiscriminant { ref place, variant_index: _ } => {
  69                 self.mutate_place(location, place, Shallow(None), JustWrite);
  70             }
  71             StatementKind::InlineAsm(ref 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::AscribeUserType(..)
  97             | StatementKind::Retag { .. }
  98             | StatementKind::StorageLive(..) => {
  99                 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
 100                 // to borrow check.
 101             }
 102             StatementKind::StorageDead(local) => {
 103                 self.access_place(
 104                     location,
 105                     &Place::from(local),
 106                     (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
 107                     LocalMutationIsAllowed::Yes,
 108                 );
 109             }
 110         }
 111
 112         self.super_statement(statement, location);
 113     }
 114
 115     fn visit_terminator_kind(&mut self, kind: &TerminatorKind<'tcx>, location: Location) {
 116         self.check_activations(location);
 117
 118         match kind {
 119             TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => {
 120                 self.consume_operand(location, discr);
 121             }
 122             TerminatorKind::Drop { location: ref drop_place, target: _, unwind: _ } => {
 123                 self.access_place(
 124                     location,
 125                     drop_place,
 126                     (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
 127                     LocalMutationIsAllowed::Yes,
 128                 );
 129             }
 130             TerminatorKind::DropAndReplace {
 131                 location: ref drop_place,
 132                 value: ref new_value,
 133                 target: _,
 134                 unwind: _,
 135             } => {
 136                 self.mutate_place(location, drop_place, Deep, JustWrite);
 137                 self.consume_operand(location, new_value);
 138             }
 139             TerminatorKind::Call {
 140                 ref func,
 141                 ref args,
 142                 ref destination,
 143                 cleanup: _,
 144                 from_hir_call: _,
 145             } => {
 146                 self.consume_operand(location, func);
 147                 for arg in args {
 148                     self.consume_operand(location, arg);
 149                 }
 150                 if let Some((ref dest, _ /*bb*/)) = *destination {
 151                     self.mutate_place(location, dest, Deep, JustWrite);
 152                 }
 153             }
 154             TerminatorKind::Assert { ref cond, expected: _, ref msg, target: _, cleanup: _ } => {
 155                 self.consume_operand(location, cond);
 156                 use rustc::mir::AssertKind;
 157                 if let AssertKind::BoundsCheck { ref len, ref index } = *msg {
 158                     self.consume_operand(location, len);
 159                     self.consume_operand(location, index);
 160                 }
 161             }
 162             TerminatorKind::Yield { ref value, resume, resume_arg, drop: _ } => {
 163                 self.consume_operand(location, value);
 164
 165                 // Invalidate all borrows of local places
 166                 let borrow_set = self.borrow_set.clone();
 167                 let resume = self.location_table.start_index(resume.start_location());
 168                 for i in borrow_set.borrows.indices() {
 169                     if borrow_of_local_data(&borrow_set.borrows[i].borrowed_place) {
 170                         self.all_facts.invalidates.push((resume, i));
 171                     }
 172                 }
 173
 174                 self.mutate_place(location, resume_arg, Deep, JustWrite);
 175             }
 176             TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
 177                 // Invalidate all borrows of local places
 178                 let borrow_set = self.borrow_set.clone();
 179                 let start = self.location_table.start_index(location);
 180                 for i in borrow_set.borrows.indices() {
 181                     if borrow_of_local_data(&borrow_set.borrows[i].borrowed_place) {
 182                         self.all_facts.invalidates.push((start, i));
 183                     }
 184                 }
 185             }
 186             TerminatorKind::Goto { target: _ }
 187             | TerminatorKind::Abort
 188             | TerminatorKind::Unreachable
 189             | TerminatorKind::FalseEdges { real_target: _, imaginary_target: _ }
 190             | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
 191                 // no data used, thus irrelevant to borrowck
 192             }
 193         }
 194
 195         self.super_terminator_kind(kind, location);
 196     }
 197 }
 198
 199 impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> {
 200     /// Simulates mutation of a place.
 201     fn mutate_place(
 202         &mut self,
 203         location: Location,
 204         place: &Place<'tcx>,
 205         kind: AccessDepth,
 206         _mode: MutateMode,
 207     ) {
 208         self.access_place(
 209             location,
 210             place,
 211             (kind, Write(WriteKind::Mutate)),
 212             LocalMutationIsAllowed::ExceptUpvars,
 213         );
 214     }
 215
 216     /// Simulates consumption of an operand.
 217     fn consume_operand(&mut self, location: Location, operand: &Operand<'tcx>) {
 218         match *operand {
 219             Operand::Copy(ref place) => {
 220                 self.access_place(
 221                     location,
 222                     place,
 223                     (Deep, Read(ReadKind::Copy)),
 224                     LocalMutationIsAllowed::No,
 225                 );
 226             }
 227             Operand::Move(ref place) => {
 228                 self.access_place(
 229                     location,
 230                     place,
 231                     (Deep, Write(WriteKind::Move)),
 232                     LocalMutationIsAllowed::Yes,
 233                 );
 234             }
 235             Operand::Constant(_) => {}
 236         }
 237     }
 238
 239     // Simulates consumption of an rvalue
 240     fn consume_rvalue(&mut self, location: Location, rvalue: &Rvalue<'tcx>) {
 241         match *rvalue {
 242             Rvalue::Ref(_ /*rgn*/, bk, ref place) => {
 243                 let access_kind = match bk {
 244                     BorrowKind::Shallow => {
 245                         (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
 246                     }
 247                     BorrowKind::Shared => (Deep, Read(ReadKind::Borrow(bk))),
 248                     BorrowKind::Unique | BorrowKind::Mut { .. } => {
 249                         let wk = WriteKind::MutableBorrow(bk);
 250                         if allow_two_phase_borrow(bk) {
 251                             (Deep, Reservation(wk))
 252                         } else {
 253                             (Deep, Write(wk))
 254                         }
 255                     }
 256                 };
 257
 258                 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
 259             }
 260
 261             Rvalue::AddressOf(mutability, ref place) => {
 262                 let access_kind = match mutability {
 263                     Mutability::Mut => (
 264                         Deep,
 265                         Write(WriteKind::MutableBorrow(BorrowKind::Mut {
 266                             allow_two_phase_borrow: false,
 267                         })),
 268                     ),
 269                     Mutability::Not => (Deep, Read(ReadKind::Borrow(BorrowKind::Shared))),
 270                 };
 271
 272                 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
 273             }
 274
 275             Rvalue::Use(ref operand)
 276             | Rvalue::Repeat(ref operand, _)
 277             | Rvalue::UnaryOp(_ /*un_op*/, ref operand)
 278             | Rvalue::Cast(_ /*cast_kind*/, ref operand, _ /*ty*/) => {
 279                 self.consume_operand(location, operand)
 280             }
 281
 282             Rvalue::Len(ref place) | Rvalue::Discriminant(ref place) => {
 283                 let af = match *rvalue {
 284                     Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
 285                     Rvalue::Discriminant(..) => None,
 286                     _ => unreachable!(),
 287                 };
 288                 self.access_place(
 289                     location,
 290                     place,
 291                     (Shallow(af), Read(ReadKind::Copy)),
 292                     LocalMutationIsAllowed::No,
 293                 );
 294             }
 295
 296             Rvalue::BinaryOp(_bin_op, ref operand1, ref operand2)
 297             | Rvalue::CheckedBinaryOp(_bin_op, ref operand1, ref operand2) => {
 298                 self.consume_operand(location, operand1);
 299                 self.consume_operand(location, operand2);
 300             }
 301
 302             Rvalue::NullaryOp(_op, _ty) => {}
 303
 304             Rvalue::Aggregate(_, ref operands) => {
 305                 for operand in operands {
 306                     self.consume_operand(location, operand);
 307                 }
 308             }
 309         }
 310     }
 311
 312     /// Simulates an access to a place.
 313     fn access_place(
 314         &mut self,
 315         location: Location,
 316         place: &Place<'tcx>,
 317         kind: (AccessDepth, ReadOrWrite),
 318         _is_local_mutation_allowed: LocalMutationIsAllowed,
 319     ) {
 320         let (sd, rw) = kind;
 321         // note: not doing check_access_permissions checks because they don't generate invalidates
 322         self.check_access_for_conflict(location, place, sd, rw);
 323     }
 324
 325     fn check_access_for_conflict(
 326         &mut self,
 327         location: Location,
 328         place: &Place<'tcx>,
 329         sd: AccessDepth,
 330         rw: ReadOrWrite,
 331     ) {
 332         debug!(
 333             "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \
 334              rw={:?})",
 335             location, place, sd, rw,
 336         );
 337         let tcx = self.tcx;
 338         let body = self.body;
 339         let borrow_set = self.borrow_set.clone();
 340         let indices = self.borrow_set.borrows.indices();
 341         each_borrow_involving_path(
 342             self,
 343             tcx,
 344             body,
 345             location,
 346             (sd, place),
 347             &borrow_set.clone(),
 348             indices,
 349             |this, borrow_index, borrow| {
 350                 match (rw, borrow.kind) {
 351                     // Obviously an activation is compatible with its own
 352                     // reservation (or even prior activating uses of same
 353                     // borrow); so don't check if they interfere.
 354                     //
 355                     // NOTE: *reservations* do conflict with themselves;
 356                     // thus aren't injecting unsoundenss w/ this check.)
 357                     (Activation(_, activating), _) if activating == borrow_index => {
 358                         // Activating a borrow doesn't generate any invalidations, since we
 359                         // have already taken the reservation
 360                     }
 361
 362                     (Read(_), BorrowKind::Shallow)
 363                     | (Read(_), BorrowKind::Shared)
 364                     | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Unique)
 365                     | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Mut { .. }) => {
 366                         // Reads don't invalidate shared or shallow borrows
 367                     }
 368
 369                     (Read(_), BorrowKind::Unique) | (Read(_), BorrowKind::Mut { .. }) => {
 370                         // Reading from mere reservations of mutable-borrows is OK.
 371                         if !is_active(&this.dominators, borrow, location) {
 372                             // If the borrow isn't active yet, reads don't invalidate it
 373                             assert!(allow_two_phase_borrow(borrow.kind));
 374                             return Control::Continue;
 375                         }
 376
 377                         // Unique and mutable borrows are invalidated by reads from any
 378                         // involved path
 379                         this.generate_invalidates(borrow_index, location);
 380                     }
 381
 382                     (Reservation(_), _) | (Activation(_, _), _) | (Write(_), _) => {
 383                         // unique or mutable borrows are invalidated by writes.
 384                         // Reservations count as writes since we need to check
 385                         // that activating the borrow will be OK
 386                         // FIXME(bob_twinkles) is this actually the right thing to do?
 387                         this.generate_invalidates(borrow_index, location);
 388                     }
 389                 }
 390                 Control::Continue
 391             },
 392         );
 393     }
 394
 395     /// Generates a new `invalidates(L, B)` fact.
 396     fn generate_invalidates(&mut self, b: BorrowIndex, l: Location) {
 397         let lidx = self.location_table.start_index(l);
 398         self.all_facts.invalidates.push((lidx, b));
 399     }
 400
 401     fn check_activations(&mut self, location: Location) {
 402         // Two-phase borrow support: For each activation that is newly
 403         // generated at this statement, check if it interferes with
 404         // another borrow.
 405         for &borrow_index in self.borrow_set.activations_at_location(location) {
 406             let borrow = &self.borrow_set[borrow_index];
 407
 408             // only mutable borrows should be 2-phase
 409             assert!(match borrow.kind {
 410                 BorrowKind::Shared | BorrowKind::Shallow => false,
 411                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
 412             });
 413
 414             self.access_place(
 415                 location,
 416                 &borrow.borrowed_place,
 417                 (Deep, Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index)),
 418                 LocalMutationIsAllowed::No,
 419             );
 420
 421             // We do not need to call `check_if_path_or_subpath_is_moved`
 422             // again, as we already called it when we made the
 423             // initial reservation.
 424         }
 425     }
 426 }