compiler/rustc_borrowck/src/invalidation.rs

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