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