src/librustc_mir/borrow_check/invalidation.rs

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