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