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::{Terminator, 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         block: BasicBlock,
  62         statement: &Statement<'tcx>,
  63         location: Location,
  64     ) {
  65         self.check_activations(location);
  66
  67         match statement.kind {
  68             StatementKind::Assign(ref lhs, ref rhs) => {
  69                 self.consume_rvalue(
  70                     ContextKind::AssignRhs.new(location),
  71                     rhs,
  72                 );
  73
  74                 self.mutate_place(
  75                     ContextKind::AssignLhs.new(location),
  76                     lhs,
  77                     Shallow(None),
  78                     JustWrite
  79                 );
  80             }
  81             StatementKind::FakeRead(_, _) => {
  82                 // Only relavent for initialized/liveness/safety checks.
  83             }
  84             StatementKind::SetDiscriminant {
  85                 ref place,
  86                 variant_index: _,
  87             } => {
  88                 self.mutate_place(
  89                     ContextKind::SetDiscrim.new(location),
  90                     place,
  91                     Shallow(None),
  92                     JustWrite,
  93                 );
  94             }
  95             StatementKind::InlineAsm(ref asm) => {
  96                 let context = ContextKind::InlineAsm.new(location);
  97                 for (o, output) in asm.asm.outputs.iter().zip(asm.outputs.iter()) {
  98                     if o.is_indirect {
  99                         // FIXME(eddyb) indirect inline asm outputs should
 100                         // be encoded through MIR place derefs instead.
 101                         self.access_place(
 102                             context,
 103                             output,
 104                             (Deep, Read(ReadKind::Copy)),
 105                             LocalMutationIsAllowed::No,
 106                         );
 107                     } else {
 108                         self.mutate_place(
 109                             context,
 110                             output,
 111                             if o.is_rw { Deep } else { Shallow(None) },
 112                             if o.is_rw { WriteAndRead } else { JustWrite },
 113                         );
 114                     }
 115                 }
 116                 for (_, input) in asm.inputs.iter() {
 117                     self.consume_operand(context, input);
 118                 }
 119             }
 120             StatementKind::Nop |
 121             StatementKind::AscribeUserType(..) |
 122             StatementKind::Retag { .. } |
 123             StatementKind::StorageLive(..) => {
 124                 // `Nop`, `AscribeUserType`, `Retag`, and `StorageLive` are irrelevant
 125                 // to borrow check.
 126             }
 127             StatementKind::StorageDead(local) => {
 128                 self.access_place(
 129                     ContextKind::StorageDead.new(location),
 130                     &Place::Base(PlaceBase::Local(local)),
 131                     (Shallow(None), Write(WriteKind::StorageDeadOrDrop)),
 132                     LocalMutationIsAllowed::Yes,
 133                 );
 134             }
 135         }
 136
 137         self.super_statement(block, statement, location);
 138     }
 139
 140     fn visit_terminator(
 141         &mut self,
 142         block: BasicBlock,
 143         terminator: &Terminator<'tcx>,
 144         location: Location
 145     ) {
 146         self.check_activations(location);
 147
 148         match terminator.kind {
 149             TerminatorKind::SwitchInt {
 150                 ref discr,
 151                 switch_ty: _,
 152                 values: _,
 153                 targets: _,
 154             } => {
 155                 self.consume_operand(ContextKind::SwitchInt.new(location), discr);
 156             }
 157             TerminatorKind::Drop {
 158                 location: ref drop_place,
 159                 target: _,
 160                 unwind: _,
 161             } => {
 162                 self.access_place(
 163                     ContextKind::Drop.new(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                     ContextKind::DropAndReplace.new(location),
 177                     drop_place,
 178                     Deep,
 179                     JustWrite,
 180                 );
 181                 self.consume_operand(
 182                     ContextKind::DropAndReplace.new(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(ContextKind::CallOperator.new(location), func);
 194                 for arg in args {
 195                     self.consume_operand(ContextKind::CallOperand.new(location), arg);
 196                 }
 197                 if let Some((ref dest, _ /*bb*/)) = *destination {
 198                     self.mutate_place(
 199                         ContextKind::CallDest.new(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(ContextKind::Assert.new(location), cond);
 214                 use rustc::mir::interpret::InterpError::BoundsCheck;
 215                 if let BoundsCheck { ref len, ref index } = *msg {
 216                     self.consume_operand(ContextKind::Assert.new(location), len);
 217                     self.consume_operand(ContextKind::Assert.new(location), index);
 218                 }
 219             }
 220             TerminatorKind::Yield {
 221                 ref value,
 222                 resume,
 223                 drop: _,
 224             } => {
 225                 self.consume_operand(ContextKind::Yield.new(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_targets: _,
 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(block, terminator, location);
 262     }
 263 }
 264
 265 impl<'cg, 'cx, 'tcx, 'gcx> InvalidationGenerator<'cx, 'tcx, 'gcx> {
 266     /// Simulates mutation of a place.
 267     fn mutate_place(
 268         &mut self,
 269         context: Context,
 270         place: &Place<'tcx>,
 271         kind: AccessDepth,
 272         _mode: MutateMode,
 273     ) {
 274         self.access_place(
 275             context,
 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         context: Context,
 286         operand: &Operand<'tcx>,
 287     ) {
 288         match *operand {
 289             Operand::Copy(ref place) => {
 290                 self.access_place(
 291                     context,
 292                     place,
 293                     (Deep, Read(ReadKind::Copy)),
 294                     LocalMutationIsAllowed::No,
 295                 );
 296             }
 297             Operand::Move(ref place) => {
 298                 self.access_place(
 299                     context,
 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         context: Context,
 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                     context,
 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(context, 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                     context,
 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(context, operand1);
 364                 self.consume_operand(context, operand2);
 365             }
 366
 367             Rvalue::NullaryOp(_op, _ty) => {
 368             }
 369
 370             Rvalue::Aggregate(_, ref operands) => {
 371                 for operand in operands {
 372                     self.consume_operand(context, operand);
 373                 }
 374             }
 375         }
 376     }
 377
 378     /// Simulates an access to a place.
 379     fn access_place(
 380         &mut self,
 381         context: Context,
 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(context, place, sd, rw);
 389     }
 390
 391     fn check_access_for_conflict(
 392         &mut self,
 393         context: Context,
 394         place: &Place<'tcx>,
 395         sd: AccessDepth,
 396         rw: ReadOrWrite,
 397     ) {
 398         debug!(
 399             "invalidation::check_access_for_conflict(context={:?}, place={:?}, sd={:?}, \
 400              rw={:?})",
 401             context,
 402             place,
 403             sd,
 404             rw,
 405         );
 406         let tcx = self.tcx;
 407         let mir = self.mir;
 408         let borrow_set = self.borrow_set.clone();
 409         let indices = self.borrow_set.borrows.indices();
 410         each_borrow_involving_path(
 411             self,
 412             tcx,
 413             mir,
 414             context,
 415             (sd, place),
 416             &borrow_set.clone(),
 417             indices,
 418             |this, borrow_index, borrow| {
 419                 match (rw, borrow.kind) {
 420                     // Obviously an activation is compatible with its own
 421                     // reservation (or even prior activating uses of same
 422                     // borrow); so don't check if they interfere.
 423                     //
 424                     // NOTE: *reservations* do conflict with themselves;
 425                     // thus aren't injecting unsoundenss w/ this check.)
 426                     (Activation(_, activating), _) if activating == borrow_index => {
 427                         // Activating a borrow doesn't generate any invalidations, since we
 428                         // have already taken the reservation
 429                     }
 430
 431                     (Read(_), BorrowKind::Shallow)
 432                     | (Read(_), BorrowKind::Shared)
 433                     | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Unique)
 434                     | (Read(ReadKind::Borrow(BorrowKind::Shallow)), BorrowKind::Mut { .. }) => {
 435                         // Reads don't invalidate shared or shallow borrows
 436                     }
 437
 438                     (Read(_), BorrowKind::Unique) | (Read(_), BorrowKind::Mut { .. }) => {
 439                         // Reading from mere reservations of mutable-borrows is OK.
 440                         if !is_active(&this.dominators, borrow, context.loc) {
 441                             // If the borrow isn't active yet, reads don't invalidate it
 442                             assert!(allow_two_phase_borrow(borrow.kind));
 443                             return Control::Continue;
 444                         }
 445
 446                         // Unique and mutable borrows are invalidated by reads from any
 447                         // involved path
 448                         this.generate_invalidates(borrow_index, context.loc);
 449                     }
 450
 451                     (Reservation(_), _)
 452                     | (Activation(_, _), _)
 453                     | (Write(_), _) => {
 454                         // unique or mutable borrows are invalidated by writes.
 455                         // Reservations count as writes since we need to check
 456                         // that activating the borrow will be OK
 457                         // FIXME(bob_twinkles) is this actually the right thing to do?
 458                         this.generate_invalidates(borrow_index, context.loc);
 459                     }
 460                 }
 461                 Control::Continue
 462             },
 463         );
 464     }
 465
 466
 467     /// Generates a new `invalidates(L, B)` fact.
 468     fn generate_invalidates(&mut self, b: BorrowIndex, l: Location) {
 469         let lidx = self.location_table.start_index(l);
 470         self.all_facts.invalidates.push((lidx, b));
 471     }
 472
 473     fn check_activations(
 474         &mut self,
 475         location: Location,
 476     ) {
 477         // Two-phase borrow support: For each activation that is newly
 478         // generated at this statement, check if it interferes with
 479         // another borrow.
 480         for &borrow_index in self.borrow_set.activations_at_location(location) {
 481             let borrow = &self.borrow_set[borrow_index];
 482
 483             // only mutable borrows should be 2-phase
 484             assert!(match borrow.kind {
 485                 BorrowKind::Shared | BorrowKind::Shallow => false,
 486                 BorrowKind::Unique | BorrowKind::Mut { .. } => true,
 487             });
 488
 489             self.access_place(
 490                 ContextKind::Activation.new(location),
 491                 &borrow.borrowed_place,
 492                 (
 493                     Deep,
 494                     Activation(WriteKind::MutableBorrow(borrow.kind), borrow_index),
 495                 ),
 496                 LocalMutationIsAllowed::No,
 497             );
 498
 499             // We do not need to call `check_if_path_or_subpath_is_moved`
 500             // again, as we already called it when we made the
 501             // initial reservation.
 502         }
 503     }
 504 }