src/stacked_borrows.rs

   1 use std::cell::RefCell;
   2
   3 use rustc::ty::{Ty, layout::Size};
   4 use rustc::mir;
   5
   6 use super::{
   7     RangeMap, EvalResult,
   8     Pointer,
   9 };
  10
  11 pub type Timestamp = u64;
  12
  13 /// Information about a potentially mutable borrow
  14 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  15 pub enum Mut {
  16   /// A unique, mutable reference
  17   Uniq(Timestamp),
  18   /// Any raw pointer, or a shared borrow with interior mutability
  19   Raw,
  20 }
  21
  22 impl Mut {
  23     #[inline(always)]
  24     fn is_raw(self) -> bool {
  25         match self {
  26             Mut::Raw => true,
  27             _ => false,
  28         }
  29     }
  30
  31     #[inline(always)]
  32     fn is_uniq(self) -> bool {
  33         match self {
  34             Mut::Uniq(_) => true,
  35             _ => false,
  36         }
  37     }
  38 }
  39
  40 /// Information about any kind of borrow
  41 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  42 pub enum Borrow {
  43   /// A mutable borrow, a raw pointer, or a shared borrow with interior mutability
  44   Mut(Mut),
  45   /// A shared borrow without interior mutability
  46   Frz(Timestamp)
  47 }
  48
  49 impl Borrow {
  50     #[inline(always)]
  51     fn is_mut(self) -> bool {
  52         match self {
  53             Borrow::Mut(_) => true,
  54             _ => false,
  55         }
  56     }
  57
  58     #[inline(always)]
  59     fn is_uniq(self) -> bool {
  60         match self {
  61             Borrow::Mut(Mut::Uniq(_)) => true,
  62             _ => false,
  63         }
  64     }
  65 }
  66
  67 /// An item in the borrow stack
  68 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  69 pub enum BorStackItem {
  70   /// Defines which references are permitted to mutate *if* the location is not frozen
  71   Mut(Mut),
  72   /// A barrier, tracking the function it belongs to by its index on the call stack
  73   FnBarrier(usize)
  74 }
  75
  76 impl Default for Borrow {
  77     fn default() -> Self {
  78         Borrow::Mut(Mut::Raw)
  79     }
  80 }
  81
  82 /// Extra global machine state
  83 #[derive(Clone, Debug)]
  84 pub struct State {
  85     clock: Timestamp
  86 }
  87
  88 impl State {
  89     pub fn new() -> State {
  90         State { clock: 0 }
  91     }
  92 }
  93
  94 /// Extra per-location state
  95 #[derive(Clone, Debug)]
  96 struct Stack {
  97     borrows: Vec<BorStackItem>, // used as a stack
  98     frozen_since: Option<Timestamp>,
  99 }
 100
 101 impl Default for Stack {
 102     fn default() -> Self {
 103         Stack {
 104             borrows: Vec::new(),
 105             frozen_since: None,
 106         }
 107     }
 108 }
 109
 110 /// Extra per-allocation state
 111 #[derive(Clone, Debug, Default)]
 112 pub struct Stacks {
 113     stacks: RefCell<RangeMap<Stack>>,
 114 }
 115
 116 /// Core operations
 117 impl<'tcx> Stack {
 118     fn check(&self, bor: Borrow) -> bool {
 119         match bor {
 120             Borrow::Frz(acc_t) =>
 121                 // Must be frozen at least as long as the `acc_t` says.
 122                 self.frozen_since.map_or(false, |loc_t| loc_t <= acc_t),
 123             Borrow::Mut(acc_m) =>
 124                 // Raw pointers are fine with frozen locations. This is important because &Cell is raw!
 125                 if self.frozen_since.is_some() {
 126                     acc_m.is_raw()
 127                 } else {
 128                     self.borrows.last().map_or(false, |&loc_itm| loc_itm == BorStackItem::Mut(acc_m))
 129                 }
 130         }
 131     }
 132
 133     /// Reactive `bor` for this stack.  If `force_mut` is set, we want to aggressively
 134     /// unfreeze this location (because we are about to push a `Uniq`).
 135     fn reactivate(&mut self, bor: Borrow, force_mut: bool) -> EvalResult<'tcx> {
 136         assert!(!force_mut || bor.is_mut()); // if `force_mut` is set, this must be a mutable borrow
 137         // Do NOT change anything if `bor` is already active -- in particular, if
 138         // it is a `Mut(Raw)` and we are frozen.
 139         if !force_mut && self.check(bor) {
 140             return Ok(());
 141         }
 142
 143         let acc_m = match bor {
 144             Borrow::Frz(_) => return err!(MachineError(format!("Location should be frozen but it is not"))),
 145             Borrow::Mut(acc_m) => acc_m,
 146         };
 147         // We definitely have to unfreeze this, even if we use the topmost item.
 148         self.frozen_since = None;
 149         // Pop until we see the one we are looking for.
 150         while let Some(&itm) = self.borrows.last() {
 151             match itm {
 152                 BorStackItem::FnBarrier(_) => {
 153                     return err!(MachineError(format!("Trying to reactivate a borrow that lives behind a barrier")));
 154                 }
 155                 BorStackItem::Mut(loc_m) => {
 156                     if loc_m == acc_m { return Ok(()); }
 157                     self.borrows.pop();
 158                 }
 159             }
 160         }
 161         // Nothing to be found.  Simulate a "virtual raw" element at the bottom of the stack.
 162         if acc_m.is_raw() {
 163             Ok(())
 164         } else {
 165             err!(MachineError(format!("Borrow-to-reactivate does not exist on the stack")))
 166         }
 167     }
 168
 169     fn initiate(&mut self, bor: Borrow) -> EvalResult<'tcx> {
 170         match bor {
 171             Borrow::Frz(t) => {
 172                 match self.frozen_since {
 173                     None => self.frozen_since = Some(t),
 174                     Some(since) => assert!(since <= t),
 175                 }
 176             }
 177             Borrow::Mut(m) => {
 178                 match self.frozen_since {
 179                     None => self.borrows.push(BorStackItem::Mut(m)),
 180                     Some(_) =>
 181                         // FIXME: Do we want an exception for raw borrows?
 182                         return err!(MachineError(format!("Trying to mutate frozen location")))
 183                 }
 184             }
 185         }
 186         Ok(())
 187     }
 188 }
 189
 190 impl State {
 191     fn increment_clock(&mut self) -> Timestamp {
 192         self.clock += 1;
 193         self.clock
 194     }
 195 }
 196
 197 /// Machine hooks
 198 pub trait EvalContextExt<'tcx> {
 199     fn tag_reference(
 200         &mut self,
 201         ptr: Pointer<Borrow>,
 202         pointee_ty: Ty<'tcx>,
 203         size: Size,
 204         borrow_kind: mir::BorrowKind,
 205     ) -> EvalResult<'tcx, Borrow>;
 206
 207     fn tag_dereference(
 208         &self,
 209         ptr: Pointer<Borrow>,
 210         ptr_ty: Ty<'tcx>,
 211     ) -> EvalResult<'tcx, Borrow>;
 212 }
 213
 214 impl<'a, 'mir, 'tcx> EvalContextExt<'tcx> for super::MiriEvalContext<'a, 'mir, 'tcx> {
 215     fn tag_reference(
 216         &mut self,
 217         ptr: Pointer<Borrow>,
 218         pointee_ty: Ty<'tcx>,
 219         size: Size,
 220         borrow_kind: mir::BorrowKind,
 221     ) -> EvalResult<'tcx, Borrow> {
 222         let old_bor = ptr.tag;
 223         let time = self.machine.stacked_borrows.increment_clock();
 224         // FIXME This does not do enough checking when only part of the data lacks
 225         // interior mutability.
 226         let new_bor = match borrow_kind {
 227             mir::BorrowKind::Mut { .. } => Borrow::Mut(Mut::Uniq(time)),
 228             _ =>
 229                 if self.type_is_freeze(pointee_ty) {
 230                     Borrow::Frz(time)
 231                 } else {
 232                     Borrow::Mut(Mut::Raw)
 233                 }
 234         };
 235         trace!("tag_reference: Creating new tag for {:?} (pointee {}, size {}): {:?}", ptr, pointee_ty, size.bytes(), new_bor);
 236
 237         // Make sure this reference is not dangling or so
 238         self.memory.check_bounds(ptr, size, false)?;
 239
 240         // Update the stacks.  We cannot use `get_mut` becuse this might be immutable
 241         // memory.
 242         let alloc = self.memory.get(ptr.alloc_id).expect("We checked that the ptr is fine!");
 243         let mut stacks = alloc.extra.stacks.borrow_mut();
 244         for stack in stacks.iter_mut(ptr.offset, size) {
 245             if stack.check(new_bor) {
 246                 // The new borrow is already active!  This can happen when creating multiple
 247                 // shared references from the same mutable reference.  Do nothing.
 248             } else {
 249                 // FIXME: The blog post says we should `reset` if this is a local.
 250                 stack.reactivate(old_bor, /*force_mut*/new_bor.is_uniq())?;
 251                 stack.initiate(new_bor)?;
 252             }
 253         }
 254
 255         Ok(new_bor)
 256     }
 257
 258     fn tag_dereference(
 259         &self,
 260         ptr: Pointer<Borrow>,
 261         ptr_ty: Ty<'tcx>,
 262     ) -> EvalResult<'tcx, Borrow> {
 263         // If this is a raw ptr, forget about the tag.
 264         Ok(if ptr_ty.is_unsafe_ptr() {
 265             trace!("tag_dereference: Erasing tag for {:?} ({})", ptr, ptr_ty);
 266             Borrow::Mut(Mut::Raw)
 267         } else {
 268             // FIXME: Do we want to adjust the tag if it does not match the type?
 269             ptr.tag
 270         })
 271     }
 272 }