src/stacked_borrows.rs

   1 use std::cell::RefCell;
   2 use std::collections::HashSet;
   3 use std::rc::Rc;
   4 use std::fmt;
   5 use std::num::NonZeroU64;
   6
   7 use rustc::ty::{self, layout::Size};
   8 use rustc::hir::{MutMutable, MutImmutable};
   9 use rustc::mir::RetagKind;
  10
  11 use crate::{
  12     EvalResult, InterpError, MiriEvalContext, HelpersEvalContextExt, Evaluator, MutValueVisitor,
  13     MemoryKind, MiriMemoryKind, RangeMap, Allocation, AllocationExtra,
  14     Pointer, Immediate, ImmTy, PlaceTy, MPlaceTy,
  15 };
  16
  17 pub type PtrId = NonZeroU64;
  18 pub type CallId = NonZeroU64;
  19
  20 /// Tracking pointer provenance
  21 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  22 pub enum Tag {
  23     Tagged(PtrId),
  24     Untagged,
  25 }
  26
  27 impl fmt::Display for Tag {
  28     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  29         match self {
  30             Tag::Tagged(id) => write!(f, "{}", id),
  31             Tag::Untagged => write!(f, "<untagged>"),
  32         }
  33     }
  34 }
  35
  36 /// Indicates which permission is granted (by this item to some pointers)
  37 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  38 pub enum Permission {
  39     /// Grants unique mutable access.
  40     Unique,
  41     /// Grants shared mutable access.
  42     SharedReadWrite,
  43     /// Greants shared read-only access.
  44     SharedReadOnly,
  45 }
  46
  47 /// An item in the per-location borrow stack.
  48 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  49 pub struct Item {
  50     /// The permission this item grants.
  51     perm: Permission,
  52     /// The pointers the permission is granted to.
  53     tag: Tag,
  54     /// An optional protector, ensuring the item cannot get popped until `CallId` is over.
  55     protector: Option<CallId>,
  56 }
  57
  58 impl fmt::Display for Item {
  59     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  60         write!(f, "[{:?} for {}", self.perm, self.tag)?;
  61         if let Some(call) = self.protector {
  62             write!(f, " (call {})", call)?;
  63         }
  64         write!(f, "]")?;
  65         Ok(())
  66     }
  67 }
  68
  69 /// Extra per-location state.
  70 #[derive(Clone, Debug, PartialEq, Eq)]
  71 pub struct Stack {
  72     /// Used *mostly* as a stack; never empty.
  73     /// We sometimes push into the middle but never remove from the middle.
  74     /// The same tag may occur multiple times, e.g. from a two-phase borrow.
  75     /// Invariants:
  76     /// * Above a `SharedReadOnly` there can only be more `SharedReadOnly`.
  77     borrows: Vec<Item>,
  78 }
  79
  80
  81 /// Extra per-allocation state.
  82 #[derive(Clone, Debug)]
  83 pub struct Stacks {
  84     // Even reading memory can have effects on the stack, so we need a `RefCell` here.
  85     stacks: RefCell<RangeMap<Stack>>,
  86     // Pointer to global state
  87     global: MemoryState,
  88 }
  89
  90 /// Extra global state, available to the memory access hooks.
  91 #[derive(Debug)]
  92 pub struct GlobalState {
  93     next_ptr_id: PtrId,
  94     next_call_id: CallId,
  95     active_calls: HashSet<CallId>,
  96 }
  97 pub type MemoryState = Rc<RefCell<GlobalState>>;
  98
  99 /// Indicates which kind of access is being performed.
 100 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 101 pub enum AccessKind {
 102     Read,
 103     Write,
 104 }
 105
 106 impl fmt::Display for AccessKind {
 107     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 108         match self {
 109             AccessKind::Read => write!(f, "read"),
 110             AccessKind::Write => write!(f, "write"),
 111         }
 112     }
 113 }
 114
 115 /// Indicates which kind of reference is being created.
 116 /// Used by high-level `reborrow` to compute which permissions to grant to the
 117 /// new pointer.
 118 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 119 pub enum RefKind {
 120     /// `&mut` and `Box`.
 121     Unique,
 122     /// `&` with or without interior mutability.
 123     Shared,
 124     /// `*mut`/`*const` (raw pointers).
 125     Raw { mutable: bool },
 126 }
 127
 128 impl fmt::Display for RefKind {
 129     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 130         match self {
 131             RefKind::Unique => write!(f, "unique"),
 132             RefKind::Shared => write!(f, "shared"),
 133             RefKind::Raw { mutable: true } => write!(f, "raw (mutable)"),
 134             RefKind::Raw { mutable: false } => write!(f, "raw (constant)"),
 135         }
 136     }
 137 }
 138
 139 /// Utilities for initialization and ID generation
 140 impl Default for GlobalState {
 141     fn default() -> Self {
 142         GlobalState {
 143             next_ptr_id: NonZeroU64::new(1).unwrap(),
 144             next_call_id: NonZeroU64::new(1).unwrap(),
 145             active_calls: HashSet::default(),
 146         }
 147     }
 148 }
 149
 150 impl GlobalState {
 151     pub fn new_ptr(&mut self) -> PtrId {
 152         let id = self.next_ptr_id;
 153         self.next_ptr_id = NonZeroU64::new(id.get() + 1).unwrap();
 154         id
 155     }
 156
 157     pub fn new_call(&mut self) -> CallId {
 158         let id = self.next_call_id;
 159         trace!("new_call: Assigning ID {}", id);
 160         self.active_calls.insert(id);
 161         self.next_call_id = NonZeroU64::new(id.get() + 1).unwrap();
 162         id
 163     }
 164
 165     pub fn end_call(&mut self, id: CallId) {
 166         assert!(self.active_calls.remove(&id));
 167     }
 168
 169     fn is_active(&self, id: CallId) -> bool {
 170         self.active_calls.contains(&id)
 171     }
 172 }
 173
 174 // # Stacked Borrows Core Begin
 175
 176 /// We need to make at least the following things true:
 177 ///
 178 /// U1: After creating a `Uniq`, it is at the top.
 179 /// U2: If the top is `Uniq`, accesses must be through that `Uniq` or remove it it.
 180 /// U3: If an access happens with a `Uniq`, it requires the `Uniq` to be in the stack.
 181 ///
 182 /// F1: After creating a `&`, the parts outside `UnsafeCell` have our `SharedReadOnly` on top.
 183 /// F2: If a write access happens, it pops the `SharedReadOnly`.  This has three pieces:
 184 ///     F2a: If a write happens granted by an item below our `SharedReadOnly`, the `SharedReadOnly`
 185 ///          gets popped.
 186 ///     F2b: No `SharedReadWrite` or `Unique` will ever be added on top of our `SharedReadOnly`.
 187 /// F3: If an access happens with an `&` outside `UnsafeCell`,
 188 ///     it requires the `SharedReadOnly` to still be in the stack.
 189
 190 impl Default for Tag {
 191     #[inline(always)]
 192     fn default() -> Tag {
 193         Tag::Untagged
 194     }
 195 }
 196
 197 /// Core relations on `Permission` define which accesses are allowed:
 198 /// On every access, we try to find a *granting* item, and then we remove all
 199 /// *incompatible* items above it.
 200 impl Permission {
 201     /// This defines for a given permission, whether it permits the given kind of access.
 202     fn grants(self, access: AccessKind) -> bool {
 203         match (self, access) {
 204             // Unique and SharedReadWrite allow any kind of access.
 205             (Permission::Unique, _) |
 206             (Permission::SharedReadWrite, _) =>
 207                 true,
 208             // SharedReadOnly only permits read access.
 209             (Permission::SharedReadOnly, AccessKind::Read) =>
 210                 true,
 211             (Permission::SharedReadOnly, AccessKind::Write) =>
 212                 false,
 213         }
 214     }
 215
 216     /// This defines for a given permission, which other permissions it can tolerate "above" itself
 217     /// when it is written to.
 218     /// If true, then `other` is allowed to remain on top of `self` when a write access happens.
 219     fn write_compatible_with(self, other: Permission) -> bool {
 220         // Only writes to SharedRW can tolerate any other items above them, and they only
 221         // tolerate other SharedRW.  So, basically, searching the first write-incompatible item above X treats
 222         // consecutive SharedRW as one "group", and skips to the first item outside X's group.
 223         return self == Permission::SharedReadWrite && other == Permission::SharedReadWrite;
 224     }
 225 }
 226
 227 /// Core per-location operations: access, dealloc, reborrow.
 228 impl<'tcx> Stack {
 229     /// Find the item granting the given kind of access to the given tag, and return where
 230     /// *the first write-incompatible item above it* is on the stack.
 231     fn check_granting(&self, access: AccessKind, tag: Tag) -> Option<usize> {
 232         let (perm, idx) = self.borrows.iter()
 233             .enumerate() // we also need to know *where* in the stack
 234             .rev() // search top-to-bottom
 235             // Return permission of first item that grants access.
 236             // We require a permission with the right tag, ensuring U3 and F3.
 237             .find_map(|(idx, item)|
 238                 if item.perm.grants(access) && tag == item.tag {
 239                     Some((item.perm, idx))
 240                 } else {
 241                     None
 242                 }
 243             )?;
 244
 245         let mut first_incompatible_idx = idx+1;
 246         while let Some(item) = self.borrows.get(first_incompatible_idx) {
 247             if perm.write_compatible_with(item.perm) {
 248                 // Keep this, check next.
 249                 first_incompatible_idx += 1;
 250             } else {
 251                 // Found it!
 252                 break;
 253             }
 254         }
 255         return Some(first_incompatible_idx);
 256     }
 257
 258     /// Test if a memory `access` using pointer tagged `tag` is granted.
 259     /// If yes, return the index of the item that granted it.
 260     fn access(
 261         &mut self,
 262         access: AccessKind,
 263         tag: Tag,
 264         global: &GlobalState,
 265     ) -> EvalResult<'tcx> {
 266         // Two main steps: Find granting item, remove incompatible items above.
 267
 268         // Step 1: Find granting item.
 269         let first_incompatible_idx = self.check_granting(access, tag)
 270             .ok_or_else(|| InterpError::MachineError(format!(
 271                 "no item granting {} access to tag {} found in borrow stack",
 272                 access, tag,
 273             )))?;
 274
 275         // Step 2: Remove incompatible items above them.  Make sure we do not remove protected
 276         // items.  Behavior differs for reads and writes.
 277         //
 278         // For writes, this is a simple stack, where everything starting with the first incompatible item
 279         // gets removed. This makes sure read-only and unique pointers become invalid on write accesses
 280         // (ensures F2a, and ensures U2 for write accesses).
 281         //
 282         // For reads, however, we just filter away the Unique items, which is sufficient to ensure U2 for read
 283         // accesses. The reason is that in `let raw = &mut *x as *mut _; let _val = *x;`, the second statement
 284         // would pop the `Unique` from the reborrow of the first statement, and subsequently also pop the
 285         // `SharedReadWrite` for `raw`.
 286         // This pattern occurs a lot in the standard library: create a raw pointer, then also create a shared
 287         // reference and use that.
 288         {
 289             // Implemented with indices because there does not seem to be a nice iterator and range-based
 290             // API for this.
 291             let mut cur = first_incompatible_idx;
 292             while let Some(item) = self.borrows.get(cur) {
 293                 // If this is a read, only remove Unique items!
 294                 if access == AccessKind::Read && item.perm != Permission::Unique {
 295                     // Keep this, check next.
 296                     cur += 1;
 297                 } else {
 298                     // Aha! This is a bad one, remove it, and make sure it is not protected.
 299                     let item = self.borrows.remove(cur);
 300                     if let Some(call) = item.protector {
 301                         if global.is_active(call) {
 302                             return err!(MachineError(format!(
 303                                 "not granting {} access to tag {} because incompatible item {} is protected",
 304                                 access, tag, item
 305                             )));
 306                         }
 307                     }
 308                     trace!("access: removing item {}", item);
 309                 }
 310             }
 311         }
 312
 313         // Done.
 314         Ok(())
 315     }
 316
 317     /// Deallocate a location: Like a write access, but also there must be no
 318     /// active protectors at all.
 319     fn dealloc(
 320         &mut self,
 321         tag: Tag,
 322         global: &GlobalState,
 323     ) -> EvalResult<'tcx> {
 324         // Step 1: Find granting item.
 325         self.check_granting(AccessKind::Write, tag)
 326             .ok_or_else(|| InterpError::MachineError(format!(
 327                 "no item granting write access for deallocation to tag {} found in borrow stack",
 328                 tag,
 329             )))?;
 330
 331         // We must make sure there are no protected items remaining on the stack.
 332         // Also clear the stack, no more accesses are possible.
 333         for item in self.borrows.drain(..) {
 334             if let Some(call) = item.protector {
 335                 if global.is_active(call) {
 336                     return err!(MachineError(format!(
 337                         "deallocating with active protector ({})", call
 338                     )))
 339                 }
 340             }
 341         }
 342
 343         Ok(())
 344     }
 345
 346     /// `reborrow` helper function: test that the stack invariants are still maintained.
 347     fn test_invariants(&self) {
 348         let mut saw_shared_read_only = false;
 349         for item in self.borrows.iter() {
 350             match item.perm {
 351                 Permission::SharedReadOnly => {
 352                     saw_shared_read_only = true;
 353                 }
 354                 // Otherwise, if we saw one before, that's a bug.
 355                 perm if saw_shared_read_only => {
 356                     bug!("Found {:?} on top of a SharedReadOnly!", perm);
 357                 }
 358                 _ => {}
 359             }
 360         }
 361     }
 362
 363     /// Derived a new pointer from one with the given tag.
 364     /// `weak` controls whether this operation is weak or strong: weak granting does not act as
 365     /// an access, and they add the new item directly on top of the one it is derived
 366     /// from instead of all the way at the top of the stack.
 367     fn grant(
 368         &mut self,
 369         derived_from: Tag,
 370         weak: bool,
 371         new: Item,
 372         global: &GlobalState,
 373     ) -> EvalResult<'tcx> {
 374         // Figure out which access `perm` corresponds to.
 375         let access = if new.perm.grants(AccessKind::Write) {
 376             AccessKind::Write
 377         } else {
 378             AccessKind::Read
 379         };
 380         // Now we figure out which item grants our parent (`derived_from`) this kind of access.
 381         // We use that to determine where to put the new item.
 382         let first_incompatible_idx = self.check_granting(access, derived_from)
 383             .ok_or_else(|| InterpError::MachineError(format!(
 384                 "no item to reborrow for {:?} from tag {} found in borrow stack", new.perm, derived_from,
 385             )))?;
 386
 387         // Compute where to put the new item.
 388         // Either way, we ensure that we insert the new item in a way that between
 389         // `derived_from` and the new one, there are only items *compatible with* `derived_from`.
 390         let new_idx = if weak {
 391             // A weak SharedReadOnly reborrow might be added below other items, violating the
 392             // invariant that only SharedReadOnly can sit on top of SharedReadOnly.
 393             assert!(new.perm != Permission::SharedReadOnly, "Weak SharedReadOnly reborrows don't work");
 394             // A very liberal reborrow because the new pointer does not expect any kind of aliasing guarantee.
 395             // Just insert new permission as child of old permission, and maintain everything else.
 396             // This inserts "as far down as possible", which is good because it makes this pointer as
 397             // long-lived as possible *and* we want all the items that are incompatible with this
 398             // to actually get removed from the stack.  If we pushed a `SharedReadWrite` on top of
 399             // a `SharedReadOnly`, we'd violate the invariant that `SaredReadOnly` are at the top
 400             // and we'd allow write access without invalidating frozen shared references!
 401             // This ensures F2b for `SharedReadWrite` by adding the new item below any
 402             // potentially existing `SharedReadOnly`.
 403             first_incompatible_idx
 404         } else {
 405             // A "safe" reborrow for a pointer that actually expects some aliasing guarantees.
 406             // Here, creating a reference actually counts as an access, and pops incompatible
 407             // stuff off the stack.
 408             // This ensures F2b for `Unique`, by removing offending `SharedReadOnly`.
 409             self.access(access, derived_from, global)?;
 410             if access == AccessKind::Write {
 411                 // For write accesses, the position is the same as what it would have been weakly!
 412                 assert_eq!(first_incompatible_idx, self.borrows.len());
 413             }
 414
 415             // We insert "as far up as possible": We know only compatible items are remaining
 416             // on top of `derived_from`, and we want the new item at the top so that we
 417             // get the strongest possible guarantees.
 418             // This ensures U1 and F1.
 419             self.borrows.len()
 420         };
 421
 422         // Put the new item there. As an optimization, deduplicate if it is equal to one of its new neighbors.
 423         if self.borrows[new_idx-1] == new || self.borrows.get(new_idx) == Some(&new) {
 424             // Optimization applies, done.
 425             trace!("reborrow: avoiding adding redundant item {}", new);
 426         } else {
 427             trace!("reborrow: adding item {}", new);
 428             self.borrows.insert(new_idx, new);
 429         }
 430
 431         // Make sure that after all this, the stack's invariant is still maintained.
 432         if cfg!(debug_assertions) {
 433             self.test_invariants();
 434         }
 435
 436         Ok(())
 437     }
 438 }
 439 // # Stacked Borrows Core End
 440
 441 /// Map per-stack operations to higher-level per-location-range operations.
 442 impl<'tcx> Stacks {
 443     /// Creates new stack with initial tag.
 444     pub(crate) fn new(
 445         size: Size,
 446         tag: Tag,
 447         extra: MemoryState,
 448     ) -> Self {
 449         let item = Item { perm: Permission::Unique, tag, protector: None };
 450         let stack = Stack {
 451             borrows: vec![item],
 452         };
 453         Stacks {
 454             stacks: RefCell::new(RangeMap::new(size, stack)),
 455             global: extra,
 456         }
 457     }
 458
 459     /// Call `f` on every stack in the range.
 460     fn for_each(
 461         &self,
 462         ptr: Pointer<Tag>,
 463         size: Size,
 464         f: impl Fn(&mut Stack, &GlobalState) -> EvalResult<'tcx>,
 465     ) -> EvalResult<'tcx> {
 466         let global = self.global.borrow();
 467         let mut stacks = self.stacks.borrow_mut();
 468         for stack in stacks.iter_mut(ptr.offset, size) {
 469             f(stack, &*global)?;
 470         }
 471         Ok(())
 472     }
 473 }
 474
 475 /// Glue code to connect with Miri Machine Hooks
 476 impl Stacks {
 477     pub fn new_allocation(
 478         size: Size,
 479         extra: &MemoryState,
 480         kind: MemoryKind<MiriMemoryKind>,
 481     ) -> (Self, Tag) {
 482         let tag = match kind {
 483             MemoryKind::Stack => {
 484                 // New unique borrow. This `Uniq` is not accessible by the program,
 485                 // so it will only ever be used when using the local directly (i.e.,
 486                 // not through a pointer). That is, whenever we directly use a local, this will pop
 487                 // everything else off the stack, invalidating all previous pointers,
 488                 // and in particular, *all* raw pointers. This subsumes the explicit
 489                 // `reset` which the blog post [1] says to perform when accessing a local.
 490                 //
 491                 // [1]: <https://www.ralfj.de/blog/2018/08/07/stacked-borrows.html>
 492                 Tag::Tagged(extra.borrow_mut().new_ptr())
 493             }
 494             _ => {
 495                 Tag::Untagged
 496             }
 497         };
 498         let stack = Stacks::new(size, tag, Rc::clone(extra));
 499         (stack, tag)
 500     }
 501 }
 502
 503 impl AllocationExtra<Tag> for Stacks {
 504     #[inline(always)]
 505     fn memory_read<'tcx>(
 506         alloc: &Allocation<Tag, Stacks>,
 507         ptr: Pointer<Tag>,
 508         size: Size,
 509     ) -> EvalResult<'tcx> {
 510         trace!("read access with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
 511         alloc.extra.for_each(ptr, size, |stack, global| {
 512             stack.access(AccessKind::Read, ptr.tag, global)?;
 513             Ok(())
 514         })
 515     }
 516
 517     #[inline(always)]
 518     fn memory_written<'tcx>(
 519         alloc: &mut Allocation<Tag, Stacks>,
 520         ptr: Pointer<Tag>,
 521         size: Size,
 522     ) -> EvalResult<'tcx> {
 523         trace!("write access with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
 524         alloc.extra.for_each(ptr, size, |stack, global| {
 525             stack.access(AccessKind::Write, ptr.tag, global)?;
 526             Ok(())
 527         })
 528     }
 529
 530     #[inline(always)]
 531     fn memory_deallocated<'tcx>(
 532         alloc: &mut Allocation<Tag, Stacks>,
 533         ptr: Pointer<Tag>,
 534         size: Size,
 535     ) -> EvalResult<'tcx> {
 536         trace!("deallocation with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
 537         alloc.extra.for_each(ptr, size, |stack, global| {
 538             stack.dealloc(ptr.tag, global)
 539         })
 540     }
 541 }
 542
 543 /// Retagging/reborrowing.  There is some policy in here, such as which permissions
 544 /// to grant for which references, when to add protectors, and how to realize two-phase
 545 /// borrows in terms of the primitives above.
 546 impl<'a, 'mir, 'tcx> EvalContextPrivExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
 547 trait EvalContextPrivExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
 548     fn reborrow(
 549         &mut self,
 550         place: MPlaceTy<'tcx, Tag>,
 551         size: Size,
 552         kind: RefKind,
 553         new_tag: Tag,
 554         force_weak: bool,
 555         protect: bool,
 556     ) -> EvalResult<'tcx> {
 557         let this = self.eval_context_mut();
 558         let protector = if protect { Some(this.frame().extra) } else { None };
 559         let ptr = place.ptr.to_ptr()?;
 560         trace!("reborrow: {:?} reference {} derived from {} (pointee {}): {:?}, size {}",
 561             kind, new_tag, ptr.tag, place.layout.ty, ptr, size.bytes());
 562
 563         // Get the allocation. It might not be mutable, so we cannot use `get_mut`.
 564         let alloc = this.memory().get(ptr.alloc_id)?;
 565         alloc.check_bounds(this, ptr, size)?;
 566         // Update the stacks.
 567         // Make sure that raw pointers and mutable shared references are reborrowed "weak":
 568         // There could be existing unique pointers reborrowed from them that should remain valid!
 569         let perm = match kind {
 570             RefKind::Unique => Permission::Unique,
 571             RefKind::Raw { mutable: true } => Permission::SharedReadWrite,
 572             RefKind::Shared | RefKind::Raw { mutable: false } => {
 573                 // Shared references and *const are a whole different kind of game, the
 574                 // permission is not uniform across the entire range!
 575                 // We need a frozen-sensitive reborrow.
 576                 return this.visit_freeze_sensitive(place, size, |cur_ptr, size, frozen| {
 577                     // We are only ever `SharedReadOnly` inside the frozen bits.
 578                     let perm = if frozen { Permission::SharedReadOnly } else { Permission::SharedReadWrite };
 579                     let weak = perm == Permission::SharedReadWrite;
 580                     let item = Item { perm, tag: new_tag, protector };
 581                     alloc.extra.for_each(cur_ptr, size, |stack, global| {
 582                         stack.grant(cur_ptr.tag, force_weak || weak, item, global)
 583                     })
 584                 });
 585             }
 586         };
 587         debug_assert_ne!(perm, Permission::SharedReadOnly, "SharedReadOnly must be used frozen-sensitive");
 588         let weak = perm == Permission::SharedReadWrite;
 589         let item = Item { perm, tag: new_tag, protector };
 590         alloc.extra.for_each(ptr, size, |stack, global| {
 591             stack.grant(ptr.tag, force_weak || weak, item, global)
 592         })
 593     }
 594
 595     /// Retags an indidual pointer, returning the retagged version.
 596     /// `mutbl` can be `None` to make this a raw pointer.
 597     fn retag_reference(
 598         &mut self,
 599         val: ImmTy<'tcx, Tag>,
 600         kind: RefKind,
 601         protect: bool,
 602         two_phase: bool,
 603     ) -> EvalResult<'tcx, Immediate<Tag>> {
 604         let this = self.eval_context_mut();
 605         // We want a place for where the ptr *points to*, so we get one.
 606         let place = this.ref_to_mplace(val)?;
 607         let size = this.size_and_align_of_mplace(place)?
 608             .map(|(size, _)| size)
 609             .unwrap_or_else(|| place.layout.size);
 610         if size == Size::ZERO {
 611             // Nothing to do for ZSTs.
 612             return Ok(*val);
 613         }
 614
 615         // Compute new borrow.
 616         let new_tag = match kind {
 617             RefKind::Raw { .. } => Tag::Untagged,
 618             _ => Tag::Tagged(this.memory().extra.borrow_mut().new_ptr()),
 619         };
 620
 621         // Reborrow.
 622         // TODO: With `two_phase == true`, this performs a weak reborrow for a `Unique`. That
 623         // can lead to some possibly surprising effects, if the parent permission is
 624         // `SharedReadWrite` then we now have a `Unique` in the middle of them, which "splits"
 625         // them in terms of what remains valid when the `Unique` gets used.  Is that really
 626         // what we want?
 627         this.reborrow(place, size, kind, new_tag, /*force_weak:*/ two_phase, protect)?;
 628         let new_place = place.replace_tag(new_tag);
 629         // Handle two-phase borrows.
 630         if two_phase {
 631             assert!(kind == RefKind::Unique, "two-phase shared borrows make no sense");
 632             // Grant read access *to the parent pointer* with the old tag *derived from the new tag* (`new_place`).
 633             // This means the old pointer has multiple items in the stack now, which otherwise cannot happen
 634             // for unique references -- but in this case it precisely expresses the semantics we want.
 635             let old_tag = place.ptr.to_ptr().unwrap().tag;
 636             this.reborrow(new_place, size, RefKind::Shared, old_tag, /*force_weak:*/ false, /*protect:*/ false)?;
 637         }
 638
 639         // Return new pointer.
 640         Ok(new_place.to_ref())
 641     }
 642 }
 643
 644 impl<'a, 'mir, 'tcx> EvalContextExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
 645 pub trait EvalContextExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
 646     fn retag(
 647         &mut self,
 648         kind: RetagKind,
 649         place: PlaceTy<'tcx, Tag>
 650     ) -> EvalResult<'tcx> {
 651         let this = self.eval_context_mut();
 652         // Determine mutability and whether to add a protector.
 653         // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
 654         // making it useless.
 655         fn qualify(ty: ty::Ty<'_>, kind: RetagKind) -> Option<(RefKind, bool)> {
 656             match ty.sty {
 657                 // References are simple.
 658                 ty::Ref(_, _, MutMutable) =>
 659                     Some((RefKind::Unique, kind == RetagKind::FnEntry)),
 660                 ty::Ref(_, _, MutImmutable) =>
 661                     Some((RefKind::Shared, kind == RetagKind::FnEntry)),
 662                 // Raw pointers need to be enabled.
 663                 ty::RawPtr(tym) if kind == RetagKind::Raw =>
 664                     Some((RefKind::Raw { mutable: tym.mutbl == MutMutable }, false)),
 665                 // Boxes do not get a protector: protectors reflect that references outlive the call
 666                 // they were passed in to; that's just not the case for boxes.
 667                 ty::Adt(..) if ty.is_box() => Some((RefKind::Unique, false)),
 668                 _ => None,
 669             }
 670         }
 671
 672         // We need a visitor to visit all references. However, that requires
 673         // a `MemPlace`, so we have a fast path for reference types that
 674         // avoids allocating.
 675         if let Some((mutbl, protector)) = qualify(place.layout.ty, kind) {
 676             // Fast path.
 677             let val = this.read_immediate(this.place_to_op(place)?)?;
 678             let val = this.retag_reference(val, mutbl, protector, kind == RetagKind::TwoPhase)?;
 679             this.write_immediate(val, place)?;
 680             return Ok(());
 681         }
 682         let place = this.force_allocation(place)?;
 683
 684         let mut visitor = RetagVisitor { ecx: this, kind };
 685         visitor.visit_value(place)?;
 686
 687         // The actual visitor.
 688         struct RetagVisitor<'ecx, 'a, 'mir, 'tcx> {
 689             ecx: &'ecx mut MiriEvalContext<'a, 'mir, 'tcx>,
 690             kind: RetagKind,
 691         }
 692         impl<'ecx, 'a, 'mir, 'tcx>
 693             MutValueVisitor<'a, 'mir, 'tcx, Evaluator<'tcx>>
 694         for
 695             RetagVisitor<'ecx, 'a, 'mir, 'tcx>
 696         {
 697             type V = MPlaceTy<'tcx, Tag>;
 698
 699             #[inline(always)]
 700             fn ecx(&mut self) -> &mut MiriEvalContext<'a, 'mir, 'tcx> {
 701                 &mut self.ecx
 702             }
 703
 704             // Primitives of reference type, that is the one thing we are interested in.
 705             fn visit_primitive(&mut self, place: MPlaceTy<'tcx, Tag>) -> EvalResult<'tcx>
 706             {
 707                 // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
 708                 // making it useless.
 709                 if let Some((mutbl, protector)) = qualify(place.layout.ty, self.kind) {
 710                     let val = self.ecx.read_immediate(place.into())?;
 711                     let val = self.ecx.retag_reference(
 712                         val,
 713                         mutbl,
 714                         protector,
 715                         self.kind == RetagKind::TwoPhase
 716                     )?;
 717                     self.ecx.write_immediate(val, place.into())?;
 718                 }
 719                 Ok(())
 720             }
 721         }
 722
 723         Ok(())
 724     }
 725 }