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