src/librustc_mir/borrow_check/nll/invalidation.rs

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