compiler/rustc_borrowck/src/invalidation.rs

   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;
   8
   9 use crate::{
  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,
  13 };
  14
  15 pub(super) fn generate_invalidates<'tcx>(
  16     tcx: TyCtxt<'tcx>,
  17     all_facts: &mut Option<AllFacts>,
  18     location_table: &LocationTable,
  19     body: &Body<'tcx>,
  20     borrow_set: &BorrowSet<'tcx>,
  21 ) {
  22     if all_facts.is_none() {
  23         // Nothing to do if we don't have any facts
  24         return;
  25     }
  26
  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 {
  31             all_facts,
  32             borrow_set,
  33             tcx,
  34             location_table,
  35             body: &body,
  36             dominators,
  37         };
  38         ig.visit_body(body);
  39     }
  40 }
  41
  42 struct InvalidationGenerator<'cx, 'tcx> {
  43     tcx: TyCtxt<'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>,
  49 }
  50
  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);
  56
  57         match &statement.kind {
  58             StatementKind::Assign(box (lhs, rhs)) => {
  59                 self.consume_rvalue(location, rhs);
  60
  61                 self.mutate_place(location, *lhs, Shallow(None));
  62             }
  63             StatementKind::FakeRead(box (_, _)) => {
  64                 // Only relevant for initialized/liveness/safety checks.
  65             }
  66             StatementKind::Intrinsic(box NonDivergingIntrinsic::Assume(op)) => {
  67                 self.consume_operand(location, op);
  68             }
  69             StatementKind::Intrinsic(box NonDivergingIntrinsic::CopyNonOverlapping(mir::CopyNonOverlapping {
  70                 ref src,
  71                 ref dst,
  72                 ref count,
  73             })) => {
  74                 self.consume_operand(location, src);
  75                 self.consume_operand(location, dst);
  76                 self.consume_operand(location, count);
  77             }
  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) => {
  85                 self.access_place(
  86                     location,
  87                     Place::from(*local),
  88                     (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
  89                     LocalMutationIsAllowed::Yes,
  90                 );
  91             }
  92             StatementKind::Nop
  93             | StatementKind::Retag { .. }
  94             | StatementKind::Deinit(..)
  95             | StatementKind::SetDiscriminant { .. } => {
  96                 bug!("Statement not allowed in this MIR phase")
  97             }
  98         }
  99
 100         self.super_statement(statement, location);
 101     }
 102
 103     fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
 104         self.check_activations(location);
 105
 106         match &terminator.kind {
 107             TerminatorKind::SwitchInt { ref discr, switch_ty: _, targets: _ } => {
 108                 self.consume_operand(location, discr);
 109             }
 110             TerminatorKind::Drop { place: drop_place, target: _, unwind: _ } => {
 111                 self.access_place(
 112                     location,
 113                     *drop_place,
 114                     (AccessDepth::Drop, Write(WriteKind::StorageDeadOrDrop)),
 115                     LocalMutationIsAllowed::Yes,
 116                 );
 117             }
 118             TerminatorKind::DropAndReplace {
 119                 place: drop_place,
 120                 value: ref new_value,
 121                 target: _,
 122                 unwind: _,
 123             } => {
 124                 self.mutate_place(location, *drop_place, Deep);
 125                 self.consume_operand(location, new_value);
 126             }
 127             TerminatorKind::Call {
 128                 ref func,
 129                 ref args,
 130                 destination,
 131                 target: _,
 132                 cleanup: _,
 133                 from_hir_call: _,
 134                 fn_span: _,
 135             } => {
 136                 self.consume_operand(location, func);
 137                 for arg in args {
 138                     self.consume_operand(location, arg);
 139                 }
 140                 self.mutate_place(location, *destination, Deep);
 141             }
 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);
 148                 }
 149             }
 150             TerminatorKind::Yield { ref value, resume, resume_arg, drop: _ } => {
 151                 self.consume_operand(location, value);
 152
 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));
 159                     }
 160                 }
 161
 162                 self.mutate_place(location, *resume_arg, Deep);
 163             }
 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));
 171                     }
 172                 }
 173             }
 174             TerminatorKind::InlineAsm {
 175                 template: _,
 176                 ref operands,
 177                 options: _,
 178                 line_spans: _,
 179                 destination: _,
 180                 cleanup: _,
 181             } => {
 182                 for op in operands {
 183                     match *op {
 184                         InlineAsmOperand::In { reg: _, ref value } => {
 185                             self.consume_operand(location, value);
 186                         }
 187                         InlineAsmOperand::Out { reg: _, late: _, place, .. } => {
 188                             if let Some(place) = place {
 189                                 self.mutate_place(location, place, Shallow(None));
 190                             }
 191                         }
 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));
 196                             }
 197                         }
 198                         InlineAsmOperand::Const { value: _ }
 199                         | InlineAsmOperand::SymFn { value: _ }
 200                         | InlineAsmOperand::SymStatic { def_id: _ } => {}
 201                     }
 202                 }
 203             }
 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
 210             }
 211         }
 212
 213         self.super_terminator(terminator, location);
 214     }
 215 }
 216
 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) {
 220         self.access_place(
 221             location,
 222             place,
 223             (kind, Write(WriteKind::Mutate)),
 224             LocalMutationIsAllowed::ExceptUpvars,
 225         );
 226     }
 227
 228     /// Simulates consumption of an operand.
 229     fn consume_operand(&mut self, location: Location, operand: &Operand<'tcx>) {
 230         match *operand {
 231             Operand::Copy(place) => {
 232                 self.access_place(
 233                     location,
 234                     place,
 235                     (Deep, Read(ReadKind::Copy)),
 236                     LocalMutationIsAllowed::No,
 237                 );
 238             }
 239             Operand::Move(place) => {
 240                 self.access_place(
 241                     location,
 242                     place,
 243                     (Deep, Write(WriteKind::Move)),
 244                     LocalMutationIsAllowed::Yes,
 245                 );
 246             }
 247             Operand::Constant(_) => {}
 248         }
 249     }
 250
 251     // Simulates consumption of an rvalue
 252     fn consume_rvalue(&mut self, location: Location, rvalue: &Rvalue<'tcx>) {
 253         match *rvalue {
 254             Rvalue::Ref(_ /*rgn*/, bk, place) => {
 255                 let access_kind = match bk {
 256                     BorrowKind::Shallow => {
 257                         (Shallow(Some(ArtificialField::ShallowBorrow)), Read(ReadKind::Borrow(bk)))
 258                     }
 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))
 264                         } else {
 265                             (Deep, Write(wk))
 266                         }
 267                     }
 268                 };
 269
 270                 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
 271             }
 272
 273             Rvalue::AddressOf(mutability, place) => {
 274                 let access_kind = match mutability {
 275                     Mutability::Mut => (
 276                         Deep,
 277                         Write(WriteKind::MutableBorrow(BorrowKind::Mut {
 278                             allow_two_phase_borrow: false,
 279                         })),
 280                     ),
 281                     Mutability::Not => (Deep, Read(ReadKind::Borrow(BorrowKind::Shared))),
 282                 };
 283
 284                 self.access_place(location, place, access_kind, LocalMutationIsAllowed::No);
 285             }
 286
 287             Rvalue::ThreadLocalRef(_) => {}
 288
 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)
 295             }
 296             Rvalue::CopyForDeref(ref place) => {
 297                 let op = &Operand::Copy(*place);
 298                 self.consume_operand(location, op);
 299             }
 300
 301             Rvalue::Len(place) | Rvalue::Discriminant(place) => {
 302                 let af = match *rvalue {
 303                     Rvalue::Len(..) => Some(ArtificialField::ArrayLength),
 304                     Rvalue::Discriminant(..) => None,
 305                     _ => unreachable!(),
 306                 };
 307                 self.access_place(
 308                     location,
 309                     place,
 310                     (Shallow(af), Read(ReadKind::Copy)),
 311                     LocalMutationIsAllowed::No,
 312                 );
 313             }
 314
 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);
 319             }
 320
 321             Rvalue::NullaryOp(_op, _ty) => {}
 322
 323             Rvalue::Aggregate(_, ref operands) => {
 324                 for operand in operands {
 325                     self.consume_operand(location, operand);
 326                 }
 327             }
 328         }
 329     }
 330
 331     /// Simulates an access to a place.
 332     fn access_place(
 333         &mut self,
 334         location: Location,
 335         place: Place<'tcx>,
 336         kind: (AccessDepth, ReadOrWrite),
 337         _is_local_mutation_allowed: LocalMutationIsAllowed,
 338     ) {
 339         let (sd, rw) = kind;
 340         // note: not doing check_access_permissions checks because they don't generate invalidates
 341         self.check_access_for_conflict(location, place, sd, rw);
 342     }
 343
 344     fn check_access_for_conflict(
 345         &mut self,
 346         location: Location,
 347         place: Place<'tcx>,
 348         sd: AccessDepth,
 349         rw: ReadOrWrite,
 350     ) {
 351         debug!(
 352             "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \
 353              rw={:?})",
 354             location, place, sd, rw,
 355         );
 356         let tcx = self.tcx;
 357         let body = self.body;
 358         let borrow_set = self.borrow_set;
 359         let indices = self.borrow_set.indices();
 360         each_borrow_involving_path(
 361             self,
 362             tcx,
 363             body,
 364             location,
 365             (sd, place),
 366             borrow_set,
 367             indices,
 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.
 373                     //
 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
 379                     }
 380
 381                     (Read(_), BorrowKind::Shallow | BorrowKind::Shared)
 382                     | (
 383                         Read(ReadKind::Borrow(BorrowKind::Shallow)),
 384                         BorrowKind::Unique | BorrowKind::Mut { .. },
 385                     ) => {
 386                         // Reads don't invalidate shared or shallow borrows
 387                     }
 388
 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;
 395                         }
 396
 397                         // Unique and mutable borrows are invalidated by reads from any
 398                         // involved path
 399                         this.emit_loan_invalidated_at(borrow_index, location);
 400                     }
 401
 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);
 408                     }
 409                 }
 410                 Control::Continue
 411             },
 412         );
 413     }
 414
 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));
 419     }
 420
 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
 424         // another borrow.
 425         for &borrow_index in self.borrow_set.activations_at_location(location) {
 426             let borrow = &self.borrow_set[borrow_index];
 427
 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,
 432             });
 433
 434             self.access_place(
 435                 location,
 436                 borrow.borrowed_place,
 437                 (Deep, Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index)),
 438                 LocalMutationIsAllowed::No,
 439             );
 440
 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.
 444         }
 445     }
 446 }