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