src/librustc_mir/borrow_check/nll/invalidation.rs

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