src/librustc_mir/dataflow/impls/borrowed_locals.rs

   1 pub use super::*;
   2
   3 use crate::dataflow::{AnalysisDomain, GenKill, GenKillAnalysis};
   4 use rustc_middle::mir::visit::Visitor;
   5 use rustc_middle::mir::*;
   6 use rustc_middle::ty::{ParamEnv, TyCtxt};
   7 use rustc_span::DUMMY_SP;
   8
   9 pub type MaybeMutBorrowedLocals<'mir, 'tcx> = MaybeBorrowedLocals<MutBorrow<'mir, 'tcx>>;
  10
  11 /// A dataflow analysis that tracks whether a pointer or reference could possibly exist that points
  12 /// to a given local.
  13 ///
  14 /// The `K` parameter determines what kind of borrows are tracked. By default,
  15 /// `MaybeBorrowedLocals` looks for *any* borrow of a local. If you are only interested in borrows
  16 /// that might allow mutation, use the `MaybeMutBorrowedLocals` type alias instead.
  17 ///
  18 /// At present, this is used as a very limited form of alias analysis. For example,
  19 /// `MaybeBorrowedLocals` is used to compute which locals are live during a yield expression for
  20 /// immovable generators. `MaybeMutBorrowedLocals` is used during const checking to prove that a
  21 /// local has not been mutated via indirect assignment (e.g., `*p = 42`), the side-effects of a
  22 /// function call or inline assembly.
  23 pub struct MaybeBorrowedLocals<K = AnyBorrow> {
  24     kind: K,
  25     ignore_borrow_on_drop: bool,
  26 }
  27
  28 impl MaybeBorrowedLocals {
  29     /// A dataflow analysis that records whether a pointer or reference exists that may alias the
  30     /// given local.
  31     pub fn all_borrows() -> Self {
  32         MaybeBorrowedLocals { kind: AnyBorrow, ignore_borrow_on_drop: false }
  33     }
  34 }
  35
  36 impl MaybeMutBorrowedLocals<'mir, 'tcx> {
  37     /// A dataflow analysis that records whether a pointer or reference exists that may *mutably*
  38     /// alias the given local.
  39     ///
  40     /// This includes `&mut` and pointers derived from an `&mut`, as well as shared borrows of
  41     /// types with interior mutability.
  42     pub fn mut_borrows_only(
  43         tcx: TyCtxt<'tcx>,
  44         body: &'mir mir::Body<'tcx>,
  45         param_env: ParamEnv<'tcx>,
  46     ) -> Self {
  47         MaybeBorrowedLocals {
  48             kind: MutBorrow { body, tcx, param_env },
  49             ignore_borrow_on_drop: false,
  50         }
  51     }
  52 }
  53
  54 impl<K> MaybeBorrowedLocals<K> {
  55     /// During dataflow analysis, ignore the borrow that may occur when a place is dropped.
  56     ///
  57     /// Drop terminators may call custom drop glue (`Drop::drop`), which takes `&mut self` as a
  58     /// parameter. In the general case, a drop impl could launder that reference into the
  59     /// surrounding environment through a raw pointer, thus creating a valid `*mut` pointing to the
  60     /// dropped local. We are not yet willing to declare this particular case UB, so we must treat
  61     /// all dropped locals as mutably borrowed for now. See discussion on [#61069].
  62     ///
  63     /// In some contexts, we know that this borrow will never occur. For example, during
  64     /// const-eval, custom drop glue cannot be run. Code that calls this should document the
  65     /// assumptions that justify ignoring `Drop` terminators in this way.
  66     ///
  67     /// [#61069]: https://github.com/rust-lang/rust/pull/61069
  68     pub fn unsound_ignore_borrow_on_drop(self) -> Self {
  69         MaybeBorrowedLocals { ignore_borrow_on_drop: true, ..self }
  70     }
  71
  72     fn transfer_function<'a, T>(&'a self, trans: &'a mut T) -> TransferFunction<'a, T, K> {
  73         TransferFunction {
  74             kind: &self.kind,
  75             trans,
  76             ignore_borrow_on_drop: self.ignore_borrow_on_drop,
  77         }
  78     }
  79 }
  80
  81 impl<K> AnalysisDomain<'tcx> for MaybeBorrowedLocals<K>
  82 where
  83     K: BorrowAnalysisKind<'tcx>,
  84 {
  85     type Idx = Local;
  86
  87     const NAME: &'static str = K::ANALYSIS_NAME;
  88
  89     fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize {
  90         body.local_decls().len()
  91     }
  92
  93     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut BitSet<Self::Idx>) {
  94         // No locals are aliased on function entry
  95     }
  96 }
  97
  98 impl<K> GenKillAnalysis<'tcx> for MaybeBorrowedLocals<K>
  99 where
 100     K: BorrowAnalysisKind<'tcx>,
 101 {
 102     fn statement_effect(
 103         &self,
 104         trans: &mut impl GenKill<Self::Idx>,
 105         statement: &mir::Statement<'tcx>,
 106         location: Location,
 107     ) {
 108         self.transfer_function(trans).visit_statement(statement, location);
 109     }
 110
 111     fn terminator_effect(
 112         &self,
 113         trans: &mut impl GenKill<Self::Idx>,
 114         terminator: &mir::Terminator<'tcx>,
 115         location: Location,
 116     ) {
 117         self.transfer_function(trans).visit_terminator(terminator, location);
 118     }
 119
 120     fn call_return_effect(
 121         &self,
 122         _trans: &mut impl GenKill<Self::Idx>,
 123         _block: mir::BasicBlock,
 124         _func: &mir::Operand<'tcx>,
 125         _args: &[mir::Operand<'tcx>],
 126         _dest_place: mir::Place<'tcx>,
 127     ) {
 128     }
 129 }
 130
 131 impl<K> BottomValue for MaybeBorrowedLocals<K> {
 132     // bottom = unborrowed
 133     const BOTTOM_VALUE: bool = false;
 134 }
 135
 136 /// A `Visitor` that defines the transfer function for `MaybeBorrowedLocals`.
 137 struct TransferFunction<'a, T, K> {
 138     trans: &'a mut T,
 139     kind: &'a K,
 140     ignore_borrow_on_drop: bool,
 141 }
 142
 143 impl<T, K> Visitor<'tcx> for TransferFunction<'a, T, K>
 144 where
 145     T: GenKill<Local>,
 146     K: BorrowAnalysisKind<'tcx>,
 147 {
 148     fn visit_statement(&mut self, stmt: &Statement<'tcx>, location: Location) {
 149         self.super_statement(stmt, location);
 150
 151         // When we reach a `StorageDead` statement, we can assume that any pointers to this memory
 152         // are now invalid.
 153         if let StatementKind::StorageDead(local) = stmt.kind {
 154             self.trans.kill(local);
 155         }
 156     }
 157
 158     fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) {
 159         self.super_rvalue(rvalue, location);
 160
 161         match rvalue {
 162             mir::Rvalue::AddressOf(mt, borrowed_place) => {
 163                 if !borrowed_place.is_indirect() && self.kind.in_address_of(*mt, *borrowed_place) {
 164                     self.trans.gen(borrowed_place.local);
 165                 }
 166             }
 167
 168             mir::Rvalue::Ref(_, kind, borrowed_place) => {
 169                 if !borrowed_place.is_indirect() && self.kind.in_ref(*kind, *borrowed_place) {
 170                     self.trans.gen(borrowed_place.local);
 171                 }
 172             }
 173
 174             mir::Rvalue::Cast(..)
 175             | mir::Rvalue::Use(..)
 176             | mir::Rvalue::ThreadLocalRef(..)
 177             | mir::Rvalue::Repeat(..)
 178             | mir::Rvalue::Len(..)
 179             | mir::Rvalue::BinaryOp(..)
 180             | mir::Rvalue::CheckedBinaryOp(..)
 181             | mir::Rvalue::NullaryOp(..)
 182             | mir::Rvalue::UnaryOp(..)
 183             | mir::Rvalue::Discriminant(..)
 184             | mir::Rvalue::Aggregate(..) => {}
 185         }
 186     }
 187
 188     fn visit_terminator(&mut self, terminator: &mir::Terminator<'tcx>, location: Location) {
 189         self.super_terminator(terminator, location);
 190
 191         match terminator.kind {
 192             mir::TerminatorKind::Drop { place: dropped_place, .. }
 193             | mir::TerminatorKind::DropAndReplace { place: dropped_place, .. } => {
 194                 // See documentation for `unsound_ignore_borrow_on_drop` for an explanation.
 195                 if !self.ignore_borrow_on_drop {
 196                     self.trans.gen(dropped_place.local);
 197                 }
 198             }
 199
 200             TerminatorKind::Abort
 201             | TerminatorKind::Assert { .. }
 202             | TerminatorKind::Call { .. }
 203             | TerminatorKind::FalseEdge { .. }
 204             | TerminatorKind::FalseUnwind { .. }
 205             | TerminatorKind::GeneratorDrop
 206             | TerminatorKind::Goto { .. }
 207             | TerminatorKind::InlineAsm { .. }
 208             | TerminatorKind::Resume
 209             | TerminatorKind::Return
 210             | TerminatorKind::SwitchInt { .. }
 211             | TerminatorKind::Unreachable
 212             | TerminatorKind::Yield { .. } => {}
 213         }
 214     }
 215 }
 216
 217 pub struct AnyBorrow;
 218
 219 pub struct MutBorrow<'mir, 'tcx> {
 220     tcx: TyCtxt<'tcx>,
 221     body: &'mir Body<'tcx>,
 222     param_env: ParamEnv<'tcx>,
 223 }
 224
 225 impl MutBorrow<'mir, 'tcx> {
 226     /// `&` and `&raw` only allow mutation if the borrowed place is `!Freeze`.
 227     ///
 228     /// This assumes that it is UB to take the address of a struct field whose type is
 229     /// `Freeze`, then use pointer arithmetic to derive a pointer to a *different* field of
 230     /// that same struct whose type is `!Freeze`. If we decide that this is not UB, we will
 231     /// have to check the type of the borrowed **local** instead of the borrowed **place**
 232     /// below. See [rust-lang/unsafe-code-guidelines#134].
 233     ///
 234     /// [rust-lang/unsafe-code-guidelines#134]: https://github.com/rust-lang/unsafe-code-guidelines/issues/134
 235     fn shared_borrow_allows_mutation(&self, place: Place<'tcx>) -> bool {
 236         !place.ty(self.body, self.tcx).ty.is_freeze(self.tcx, self.param_env, DUMMY_SP)
 237     }
 238 }
 239
 240 pub trait BorrowAnalysisKind<'tcx> {
 241     const ANALYSIS_NAME: &'static str;
 242
 243     fn in_address_of(&self, mt: Mutability, place: Place<'tcx>) -> bool;
 244     fn in_ref(&self, kind: mir::BorrowKind, place: Place<'tcx>) -> bool;
 245 }
 246
 247 impl BorrowAnalysisKind<'tcx> for AnyBorrow {
 248     const ANALYSIS_NAME: &'static str = "maybe_borrowed_locals";
 249
 250     fn in_ref(&self, _: mir::BorrowKind, _: Place<'_>) -> bool {
 251         true
 252     }
 253     fn in_address_of(&self, _: Mutability, _: Place<'_>) -> bool {
 254         true
 255     }
 256 }
 257
 258 impl BorrowAnalysisKind<'tcx> for MutBorrow<'mir, 'tcx> {
 259     const ANALYSIS_NAME: &'static str = "maybe_mut_borrowed_locals";
 260
 261     fn in_ref(&self, kind: mir::BorrowKind, place: Place<'tcx>) -> bool {
 262         match kind {
 263             mir::BorrowKind::Mut { .. } => true,
 264             mir::BorrowKind::Shared | mir::BorrowKind::Shallow | mir::BorrowKind::Unique => {
 265                 self.shared_borrow_allows_mutation(place)
 266             }
 267         }
 268     }
 269
 270     fn in_address_of(&self, mt: Mutability, place: Place<'tcx>) -> bool {
 271         match mt {
 272             Mutability::Mut => true,
 273             Mutability::Not => self.shared_borrow_allows_mutation(place),
 274         }
 275     }
 276 }