src/librustc_mir/interpret/eval_context.rs

   1 use std::cell::Cell;
   2 use std::fmt::Write;
   3 use std::mem;
   4
   5 use rustc::hir::def::DefKind;
   6 use rustc::hir::def_id::DefId;
   7 use rustc::ich::StableHashingContext;
   8 use rustc::mir;
   9 use rustc::mir::interpret::{
  10     sign_extend, truncate, AllocId, FrameInfo, GlobalId, InterpResult, Pointer, Scalar,
  11 };
  12 use rustc::ty::layout::{self, Align, HasDataLayout, LayoutOf, Size, TyLayout};
  13 use rustc::ty::query::TyCtxtAt;
  14 use rustc::ty::subst::SubstsRef;
  15 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
  16 use rustc_data_structures::fx::FxHashMap;
  17 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  18 use rustc_index::vec::IndexVec;
  19 use rustc_macros::HashStable;
  20 use syntax::source_map::{self, Span, DUMMY_SP};
  21
  22 use super::{
  23     Immediate, MPlaceTy, Machine, MemPlace, Memory, OpTy, Operand, Place, PlaceTy,
  24     ScalarMaybeUndef, StackPopInfo,
  25 };
  26
  27 pub struct InterpCx<'mir, 'tcx, M: Machine<'mir, 'tcx>> {
  28     /// Stores the `Machine` instance.
  29     pub machine: M,
  30
  31     /// The results of the type checker, from rustc.
  32     pub tcx: TyCtxtAt<'tcx>,
  33
  34     /// Bounds in scope for polymorphic evaluations.
  35     pub(crate) param_env: ty::ParamEnv<'tcx>,
  36
  37     /// The virtual memory system.
  38     pub memory: Memory<'mir, 'tcx, M>,
  39
  40     /// The virtual call stack.
  41     pub(crate) stack: Vec<Frame<'mir, 'tcx, M::PointerTag, M::FrameExtra>>,
  42
  43     /// A cache for deduplicating vtables
  44     pub(super) vtables:
  45         FxHashMap<(Ty<'tcx>, Option<ty::PolyExistentialTraitRef<'tcx>>), Pointer<M::PointerTag>>,
  46 }
  47
  48 /// A stack frame.
  49 #[derive(Clone)]
  50 pub struct Frame<'mir, 'tcx, Tag = (), Extra = ()> {
  51     ////////////////////////////////////////////////////////////////////////////////
  52     // Function and callsite information
  53     ////////////////////////////////////////////////////////////////////////////////
  54     /// The MIR for the function called on this frame.
  55     pub body: &'mir mir::Body<'tcx>,
  56
  57     /// The def_id and substs of the current function.
  58     pub instance: ty::Instance<'tcx>,
  59
  60     /// The span of the call site.
  61     pub span: source_map::Span,
  62
  63     /// Extra data for the machine.
  64     pub extra: Extra,
  65
  66     ////////////////////////////////////////////////////////////////////////////////
  67     // Return place and locals
  68     ////////////////////////////////////////////////////////////////////////////////
  69     /// Work to perform when returning from this function.
  70     pub return_to_block: StackPopCleanup,
  71
  72     /// The location where the result of the current stack frame should be written to,
  73     /// and its layout in the caller.
  74     pub return_place: Option<PlaceTy<'tcx, Tag>>,
  75
  76     /// The list of locals for this stack frame, stored in order as
  77     /// `[return_ptr, arguments..., variables..., temporaries...]`.
  78     /// The locals are stored as `Option<Value>`s.
  79     /// `None` represents a local that is currently dead, while a live local
  80     /// can either directly contain `Scalar` or refer to some part of an `Allocation`.
  81     pub locals: IndexVec<mir::Local, LocalState<'tcx, Tag>>,
  82
  83     ////////////////////////////////////////////////////////////////////////////////
  84     // Current position within the function
  85     ////////////////////////////////////////////////////////////////////////////////
  86     /// The block that is currently executed (or will be executed after the above call stacks
  87     /// return).
  88     /// If this is `None`, we are unwinding and this function doesn't need any clean-up.
  89     /// Just continue the same as with `Resume`.
  90     pub block: Option<mir::BasicBlock>,
  91
  92     /// The index of the currently evaluated statement.
  93     pub stmt: usize,
  94 }
  95
  96 #[derive(Clone, Eq, PartialEq, Debug, HashStable)] // Miri debug-prints these
  97 pub enum StackPopCleanup {
  98     /// Jump to the next block in the caller, or cause UB if None (that's a function
  99     /// that may never return). Also store layout of return place so
 100     /// we can validate it at that layout.
 101     /// `ret` stores the block we jump to on a normal return, while 'unwind'
 102     /// stores the block used for cleanup during unwinding
 103     Goto { ret: Option<mir::BasicBlock>, unwind: Option<mir::BasicBlock> },
 104     /// Just do nohing: Used by Main and for the box_alloc hook in miri.
 105     /// `cleanup` says whether locals are deallocated. Static computation
 106     /// wants them leaked to intern what they need (and just throw away
 107     /// the entire `ecx` when it is done).
 108     None { cleanup: bool },
 109 }
 110
 111 /// State of a local variable including a memoized layout
 112 #[derive(Clone, PartialEq, Eq, HashStable)]
 113 pub struct LocalState<'tcx, Tag = (), Id = AllocId> {
 114     pub value: LocalValue<Tag, Id>,
 115     /// Don't modify if `Some`, this is only used to prevent computing the layout twice
 116     #[stable_hasher(ignore)]
 117     pub layout: Cell<Option<TyLayout<'tcx>>>,
 118 }
 119
 120 /// Current value of a local variable
 121 #[derive(Copy, Clone, PartialEq, Eq, Debug, HashStable)] // Miri debug-prints these
 122 pub enum LocalValue<Tag = (), Id = AllocId> {
 123     /// This local is not currently alive, and cannot be used at all.
 124     Dead,
 125     /// This local is alive but not yet initialized. It can be written to
 126     /// but not read from or its address taken. Locals get initialized on
 127     /// first write because for unsized locals, we do not know their size
 128     /// before that.
 129     Uninitialized,
 130     /// A normal, live local.
 131     /// Mostly for convenience, we re-use the `Operand` type here.
 132     /// This is an optimization over just always having a pointer here;
 133     /// we can thus avoid doing an allocation when the local just stores
 134     /// immediate values *and* never has its address taken.
 135     Live(Operand<Tag, Id>),
 136 }
 137
 138 impl<'tcx, Tag: Copy + 'static> LocalState<'tcx, Tag> {
 139     pub fn access(&self) -> InterpResult<'tcx, Operand<Tag>> {
 140         match self.value {
 141             LocalValue::Dead => throw_unsup!(DeadLocal),
 142             LocalValue::Uninitialized => {
 143                 bug!("The type checker should prevent reading from a never-written local")
 144             }
 145             LocalValue::Live(val) => Ok(val),
 146         }
 147     }
 148
 149     /// Overwrite the local.  If the local can be overwritten in place, return a reference
 150     /// to do so; otherwise return the `MemPlace` to consult instead.
 151     pub fn access_mut(
 152         &mut self,
 153     ) -> InterpResult<'tcx, Result<&mut LocalValue<Tag>, MemPlace<Tag>>> {
 154         match self.value {
 155             LocalValue::Dead => throw_unsup!(DeadLocal),
 156             LocalValue::Live(Operand::Indirect(mplace)) => Ok(Err(mplace)),
 157             ref mut local @ LocalValue::Live(Operand::Immediate(_))
 158             | ref mut local @ LocalValue::Uninitialized => Ok(Ok(local)),
 159         }
 160     }
 161 }
 162
 163 impl<'mir, 'tcx, Tag, Extra> Frame<'mir, 'tcx, Tag, Extra> {
 164     /// Return the `SourceInfo` of the current instruction.
 165     pub fn current_source_info(&self) -> Option<mir::SourceInfo> {
 166         self.block.map(|block| {
 167             let block = &self.body.basic_blocks()[block];
 168             if self.stmt < block.statements.len() {
 169                 block.statements[self.stmt].source_info
 170             } else {
 171                 block.terminator().source_info
 172             }
 173         })
 174     }
 175 }
 176
 177 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> HasDataLayout for InterpCx<'mir, 'tcx, M> {
 178     #[inline]
 179     fn data_layout(&self) -> &layout::TargetDataLayout {
 180         &self.tcx.data_layout
 181     }
 182 }
 183
 184 impl<'mir, 'tcx, M> layout::HasTyCtxt<'tcx> for InterpCx<'mir, 'tcx, M>
 185 where
 186     M: Machine<'mir, 'tcx>,
 187 {
 188     #[inline]
 189     fn tcx(&self) -> TyCtxt<'tcx> {
 190         *self.tcx
 191     }
 192 }
 193
 194 impl<'mir, 'tcx, M> layout::HasParamEnv<'tcx> for InterpCx<'mir, 'tcx, M>
 195 where
 196     M: Machine<'mir, 'tcx>,
 197 {
 198     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 199         self.param_env
 200     }
 201 }
 202
 203 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> LayoutOf for InterpCx<'mir, 'tcx, M> {
 204     type Ty = Ty<'tcx>;
 205     type TyLayout = InterpResult<'tcx, TyLayout<'tcx>>;
 206
 207     #[inline]
 208     fn layout_of(&self, ty: Ty<'tcx>) -> Self::TyLayout {
 209         self.tcx
 210             .layout_of(self.param_env.and(ty))
 211             .map_err(|layout| err_inval!(Layout(layout)).into())
 212     }
 213 }
 214
 215 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
 216     pub fn new(
 217         tcx: TyCtxtAt<'tcx>,
 218         param_env: ty::ParamEnv<'tcx>,
 219         machine: M,
 220         memory_extra: M::MemoryExtra,
 221     ) -> Self {
 222         InterpCx {
 223             machine,
 224             tcx,
 225             param_env,
 226             memory: Memory::new(tcx, memory_extra),
 227             stack: Vec::new(),
 228             vtables: FxHashMap::default(),
 229         }
 230     }
 231
 232     #[inline(always)]
 233     pub fn force_ptr(
 234         &self,
 235         scalar: Scalar<M::PointerTag>,
 236     ) -> InterpResult<'tcx, Pointer<M::PointerTag>> {
 237         self.memory.force_ptr(scalar)
 238     }
 239
 240     #[inline(always)]
 241     pub fn force_bits(
 242         &self,
 243         scalar: Scalar<M::PointerTag>,
 244         size: Size,
 245     ) -> InterpResult<'tcx, u128> {
 246         self.memory.force_bits(scalar, size)
 247     }
 248
 249     /// Call this to turn untagged "global" pointers (obtained via `tcx`) into
 250     /// the *canonical* machine pointer to the allocation.  Must never be used
 251     /// for any other pointers!
 252     ///
 253     /// This represents a *direct* access to that memory, as opposed to access
 254     /// through a pointer that was created by the program.
 255     #[inline(always)]
 256     pub fn tag_static_base_pointer(&self, ptr: Pointer) -> Pointer<M::PointerTag> {
 257         self.memory.tag_static_base_pointer(ptr)
 258     }
 259
 260     #[inline(always)]
 261     pub fn stack(&self) -> &[Frame<'mir, 'tcx, M::PointerTag, M::FrameExtra>] {
 262         &self.stack
 263     }
 264
 265     #[inline(always)]
 266     pub fn cur_frame(&self) -> usize {
 267         assert!(self.stack.len() > 0);
 268         self.stack.len() - 1
 269     }
 270
 271     #[inline(always)]
 272     pub fn frame(&self) -> &Frame<'mir, 'tcx, M::PointerTag, M::FrameExtra> {
 273         self.stack.last().expect("no call frames exist")
 274     }
 275
 276     #[inline(always)]
 277     pub fn frame_mut(&mut self) -> &mut Frame<'mir, 'tcx, M::PointerTag, M::FrameExtra> {
 278         self.stack.last_mut().expect("no call frames exist")
 279     }
 280
 281     #[inline(always)]
 282     pub(super) fn body(&self) -> &'mir mir::Body<'tcx> {
 283         self.frame().body
 284     }
 285
 286     #[inline(always)]
 287     pub fn sign_extend(&self, value: u128, ty: TyLayout<'_>) -> u128 {
 288         assert!(ty.abi.is_signed());
 289         sign_extend(value, ty.size)
 290     }
 291
 292     #[inline(always)]
 293     pub fn truncate(&self, value: u128, ty: TyLayout<'_>) -> u128 {
 294         truncate(value, ty.size)
 295     }
 296
 297     #[inline]
 298     pub fn type_is_sized(&self, ty: Ty<'tcx>) -> bool {
 299         ty.is_sized(self.tcx, self.param_env)
 300     }
 301
 302     #[inline]
 303     pub fn type_is_freeze(&self, ty: Ty<'tcx>) -> bool {
 304         ty.is_freeze(*self.tcx, self.param_env, DUMMY_SP)
 305     }
 306
 307     pub fn load_mir(
 308         &self,
 309         instance: ty::InstanceDef<'tcx>,
 310         promoted: Option<mir::Promoted>,
 311     ) -> InterpResult<'tcx, mir::ReadOnlyBodyAndCache<'tcx, 'tcx>> {
 312         // do not continue if typeck errors occurred (can only occur in local crate)
 313         let did = instance.def_id();
 314         if did.is_local()
 315             && self.tcx.has_typeck_tables(did)
 316             && self.tcx.typeck_tables_of(did).tainted_by_errors
 317         {
 318             throw_inval!(TypeckError)
 319         }
 320         trace!("load mir(instance={:?}, promoted={:?})", instance, promoted);
 321         if let Some(promoted) = promoted {
 322             return Ok(self.tcx.promoted_mir(did)[promoted].unwrap_read_only());
 323         }
 324         match instance {
 325             ty::InstanceDef::Item(def_id) => {
 326                 if self.tcx.is_mir_available(did) {
 327                     Ok(self.tcx.optimized_mir(did).unwrap_read_only())
 328                 } else {
 329                     throw_unsup!(NoMirFor(self.tcx.def_path_str(def_id)))
 330                 }
 331             }
 332             _ => Ok(self.tcx.instance_mir(instance)),
 333         }
 334     }
 335
 336     /// Call this on things you got out of the MIR (so it is as generic as the current
 337     /// stack frame), to bring it into the proper environment for this interpreter.
 338     pub(super) fn subst_from_frame_and_normalize_erasing_regions<T: TypeFoldable<'tcx>>(
 339         &self,
 340         value: T,
 341     ) -> T {
 342         self.tcx.subst_and_normalize_erasing_regions(
 343             self.frame().instance.substs,
 344             self.param_env,
 345             &value,
 346         )
 347     }
 348
 349     /// The `substs` are assumed to already be in our interpreter "universe" (param_env).
 350     pub(super) fn resolve(
 351         &self,
 352         def_id: DefId,
 353         substs: SubstsRef<'tcx>,
 354     ) -> InterpResult<'tcx, ty::Instance<'tcx>> {
 355         trace!("resolve: {:?}, {:#?}", def_id, substs);
 356         trace!("param_env: {:#?}", self.param_env);
 357         trace!("substs: {:#?}", substs);
 358         ty::Instance::resolve(*self.tcx, self.param_env, def_id, substs)
 359             .ok_or_else(|| err_inval!(TooGeneric).into())
 360     }
 361
 362     pub fn layout_of_local(
 363         &self,
 364         frame: &Frame<'mir, 'tcx, M::PointerTag, M::FrameExtra>,
 365         local: mir::Local,
 366         layout: Option<TyLayout<'tcx>>,
 367     ) -> InterpResult<'tcx, TyLayout<'tcx>> {
 368         // `const_prop` runs into this with an invalid (empty) frame, so we
 369         // have to support that case (mostly by skipping all caching).
 370         match frame.locals.get(local).and_then(|state| state.layout.get()) {
 371             None => {
 372                 let layout = crate::interpret::operand::from_known_layout(layout, || {
 373                     let local_ty = frame.body.local_decls[local].ty;
 374                     let local_ty = self.tcx.subst_and_normalize_erasing_regions(
 375                         frame.instance.substs,
 376                         self.param_env,
 377                         &local_ty,
 378                     );
 379                     self.layout_of(local_ty)
 380                 })?;
 381                 if let Some(state) = frame.locals.get(local) {
 382                     // Layouts of locals are requested a lot, so we cache them.
 383                     state.layout.set(Some(layout));
 384                 }
 385                 Ok(layout)
 386             }
 387             Some(layout) => Ok(layout),
 388         }
 389     }
 390
 391     /// Returns the actual dynamic size and alignment of the place at the given type.
 392     /// Only the "meta" (metadata) part of the place matters.
 393     /// This can fail to provide an answer for extern types.
 394     pub(super) fn size_and_align_of(
 395         &self,
 396         metadata: Option<Scalar<M::PointerTag>>,
 397         layout: TyLayout<'tcx>,
 398     ) -> InterpResult<'tcx, Option<(Size, Align)>> {
 399         if !layout.is_unsized() {
 400             return Ok(Some((layout.size, layout.align.abi)));
 401         }
 402         match layout.ty.kind {
 403             ty::Adt(..) | ty::Tuple(..) => {
 404                 // First get the size of all statically known fields.
 405                 // Don't use type_of::sizing_type_of because that expects t to be sized,
 406                 // and it also rounds up to alignment, which we want to avoid,
 407                 // as the unsized field's alignment could be smaller.
 408                 assert!(!layout.ty.is_simd());
 409                 trace!("DST layout: {:?}", layout);
 410
 411                 let sized_size = layout.fields.offset(layout.fields.count() - 1);
 412                 let sized_align = layout.align.abi;
 413                 trace!(
 414                     "DST {} statically sized prefix size: {:?} align: {:?}",
 415                     layout.ty,
 416                     sized_size,
 417                     sized_align
 418                 );
 419
 420                 // Recurse to get the size of the dynamically sized field (must be
 421                 // the last field).  Can't have foreign types here, how would we
 422                 // adjust alignment and size for them?
 423                 let field = layout.field(self, layout.fields.count() - 1)?;
 424                 let (unsized_size, unsized_align) = match self.size_and_align_of(metadata, field)? {
 425                     Some(size_and_align) => size_and_align,
 426                     None => {
 427                         // A field with extern type.  If this field is at offset 0, we behave
 428                         // like the underlying extern type.
 429                         // FIXME: Once we have made decisions for how to handle size and alignment
 430                         // of `extern type`, this should be adapted.  It is just a temporary hack
 431                         // to get some code to work that probably ought to work.
 432                         if sized_size == Size::ZERO {
 433                             return Ok(None);
 434                         } else {
 435                             bug!("Fields cannot be extern types, unless they are at offset 0")
 436                         }
 437                     }
 438                 };
 439
 440                 // FIXME (#26403, #27023): We should be adding padding
 441                 // to `sized_size` (to accommodate the `unsized_align`
 442                 // required of the unsized field that follows) before
 443                 // summing it with `sized_size`. (Note that since #26403
 444                 // is unfixed, we do not yet add the necessary padding
 445                 // here. But this is where the add would go.)
 446
 447                 // Return the sum of sizes and max of aligns.
 448                 let size = sized_size + unsized_size;
 449
 450                 // Choose max of two known alignments (combined value must
 451                 // be aligned according to more restrictive of the two).
 452                 let align = sized_align.max(unsized_align);
 453
 454                 // Issue #27023: must add any necessary padding to `size`
 455                 // (to make it a multiple of `align`) before returning it.
 456                 let size = size.align_to(align);
 457
 458                 // Check if this brought us over the size limit.
 459                 if size.bytes() >= self.tcx.data_layout().obj_size_bound() {
 460                     throw_ub_format!(
 461                         "wide pointer metadata contains invalid information: \
 462                         total size is bigger than largest supported object"
 463                     );
 464                 }
 465                 Ok(Some((size, align)))
 466             }
 467             ty::Dynamic(..) => {
 468                 let vtable = metadata.expect("dyn trait fat ptr must have vtable");
 469                 // Read size and align from vtable (already checks size).
 470                 Ok(Some(self.read_size_and_align_from_vtable(vtable)?))
 471             }
 472
 473             ty::Slice(_) | ty::Str => {
 474                 let len =
 475                     metadata.expect("slice fat ptr must have length").to_machine_usize(self)?;
 476                 let elem = layout.field(self, 0)?;
 477
 478                 // Make sure the slice is not too big.
 479                 let size = elem.size.checked_mul(len, &*self.tcx).ok_or_else(|| {
 480                     err_ub_format!(
 481                         "invalid slice: \
 482                         total size is bigger than largest supported object"
 483                     )
 484                 })?;
 485                 Ok(Some((size, elem.align.abi)))
 486             }
 487
 488             ty::Foreign(_) => Ok(None),
 489
 490             _ => bug!("size_and_align_of::<{:?}> not supported", layout.ty),
 491         }
 492     }
 493     #[inline]
 494     pub fn size_and_align_of_mplace(
 495         &self,
 496         mplace: MPlaceTy<'tcx, M::PointerTag>,
 497     ) -> InterpResult<'tcx, Option<(Size, Align)>> {
 498         self.size_and_align_of(mplace.meta, mplace.layout)
 499     }
 500
 501     pub fn push_stack_frame(
 502         &mut self,
 503         instance: ty::Instance<'tcx>,
 504         span: Span,
 505         body: &'mir mir::Body<'tcx>,
 506         return_place: Option<PlaceTy<'tcx, M::PointerTag>>,
 507         return_to_block: StackPopCleanup,
 508     ) -> InterpResult<'tcx> {
 509         if self.stack.len() > 0 {
 510             info!("PAUSING({}) {}", self.cur_frame(), self.frame().instance);
 511         }
 512         ::log_settings::settings().indentation += 1;
 513
 514         // first push a stack frame so we have access to the local substs
 515         let extra = M::stack_push(self)?;
 516         self.stack.push(Frame {
 517             body,
 518             block: Some(mir::START_BLOCK),
 519             return_to_block,
 520             return_place,
 521             // empty local array, we fill it in below, after we are inside the stack frame and
 522             // all methods actually know about the frame
 523             locals: IndexVec::new(),
 524             span,
 525             instance,
 526             stmt: 0,
 527             extra,
 528         });
 529
 530         // don't allocate at all for trivial constants
 531         if body.local_decls.len() > 1 {
 532             // Locals are initially uninitialized.
 533             let dummy = LocalState { value: LocalValue::Uninitialized, layout: Cell::new(None) };
 534             let mut locals = IndexVec::from_elem(dummy, &body.local_decls);
 535             // Return place is handled specially by the `eval_place` functions, and the
 536             // entry in `locals` should never be used. Make it dead, to be sure.
 537             locals[mir::RETURN_PLACE].value = LocalValue::Dead;
 538             // Now mark those locals as dead that we do not want to initialize
 539             match self.tcx.def_kind(instance.def_id()) {
 540                 // statics and constants don't have `Storage*` statements, no need to look for them
 541                 Some(DefKind::Static) | Some(DefKind::Const) | Some(DefKind::AssocConst) => {}
 542                 _ => {
 543                     trace!("push_stack_frame: {:?}: num_bbs: {}", span, body.basic_blocks().len());
 544                     for block in body.basic_blocks() {
 545                         for stmt in block.statements.iter() {
 546                             use rustc::mir::StatementKind::{StorageDead, StorageLive};
 547                             match stmt.kind {
 548                                 StorageLive(local) | StorageDead(local) => {
 549                                     locals[local].value = LocalValue::Dead;
 550                                 }
 551                                 _ => {}
 552                             }
 553                         }
 554                     }
 555                 }
 556             }
 557             // done
 558             self.frame_mut().locals = locals;
 559         }
 560
 561         info!("ENTERING({}) {}", self.cur_frame(), self.frame().instance);
 562
 563         if self.stack.len() > *self.tcx.sess.recursion_limit.get() {
 564             throw_exhaust!(StackFrameLimitReached)
 565         } else {
 566             Ok(())
 567         }
 568     }
 569
 570     /// Jump to the given block.
 571     #[inline]
 572     pub fn go_to_block(&mut self, target: mir::BasicBlock) {
 573         let frame = self.frame_mut();
 574         frame.block = Some(target);
 575         frame.stmt = 0;
 576     }
 577
 578     /// *Return* to the given `target` basic block.
 579     /// Do *not* use for unwinding! Use `unwind_to_block` instead.
 580     ///
 581     /// If `target` is `None`, that indicates the function cannot return, so we raise UB.
 582     pub fn return_to_block(&mut self, target: Option<mir::BasicBlock>) -> InterpResult<'tcx> {
 583         if let Some(target) = target {
 584             Ok(self.go_to_block(target))
 585         } else {
 586             throw_ub!(Unreachable)
 587         }
 588     }
 589
 590     /// *Unwind* to the given `target` basic block.
 591     /// Do *not* use for returning! Use `return_to_block` instead.
 592     ///
 593     /// If `target` is `None`, that indicates the function does not need cleanup during
 594     /// unwinding, and we will just keep propagating that upwards.
 595     pub fn unwind_to_block(&mut self, target: Option<mir::BasicBlock>) {
 596         let frame = self.frame_mut();
 597         frame.block = target;
 598         frame.stmt = 0;
 599     }
 600
 601     /// Pops the current frame from the stack, deallocating the
 602     /// memory for allocated locals.
 603     ///
 604     /// If `unwinding` is `false`, then we are performing a normal return
 605     /// from a function. In this case, we jump back into the frame of the caller,
 606     /// and continue execution as normal.
 607     ///
 608     /// If `unwinding` is `true`, then we are in the middle of a panic,
 609     /// and need to unwind this frame. In this case, we jump to the
 610     /// `cleanup` block for the function, which is responsible for running
 611     /// `Drop` impls for any locals that have been initialized at this point.
 612     /// The cleanup block ends with a special `Resume` terminator, which will
 613     /// cause us to continue unwinding.
 614     pub(super) fn pop_stack_frame(&mut self, unwinding: bool) -> InterpResult<'tcx> {
 615         info!(
 616             "LEAVING({}) {} (unwinding = {})",
 617             self.cur_frame(),
 618             self.frame().instance,
 619             unwinding
 620         );
 621
 622         // Sanity check `unwinding`.
 623         assert_eq!(
 624             unwinding,
 625             match self.frame().block {
 626                 None => true,
 627                 Some(block) => self.body().basic_blocks()[block].is_cleanup,
 628             }
 629         );
 630
 631         ::log_settings::settings().indentation -= 1;
 632         let frame = self.stack.pop().expect("tried to pop a stack frame, but there were none");
 633         let stack_pop_info = M::stack_pop(self, frame.extra, unwinding)?;
 634         if let (false, StackPopInfo::StopUnwinding) = (unwinding, stack_pop_info) {
 635             bug!("Attempted to stop unwinding while there is no unwinding!");
 636         }
 637
 638         // Now where do we jump next?
 639
 640         // Determine if we leave this function normally or via unwinding.
 641         let cur_unwinding =
 642             if let StackPopInfo::StopUnwinding = stack_pop_info { false } else { unwinding };
 643
 644         // Usually we want to clean up (deallocate locals), but in a few rare cases we don't.
 645         // In that case, we return early. We also avoid validation in that case,
 646         // because this is CTFE and the final value will be thoroughly validated anyway.
 647         let (cleanup, next_block) = match frame.return_to_block {
 648             StackPopCleanup::Goto { ret, unwind } => {
 649                 (true, Some(if cur_unwinding { unwind } else { ret }))
 650             }
 651             StackPopCleanup::None { cleanup, .. } => (cleanup, None),
 652         };
 653
 654         if !cleanup {
 655             assert!(self.stack.is_empty(), "only the topmost frame should ever be leaked");
 656             assert!(next_block.is_none(), "tried to skip cleanup when we have a next block!");
 657             // Leak the locals, skip validation.
 658             return Ok(());
 659         }
 660
 661         // Cleanup: deallocate all locals that are backed by an allocation.
 662         for local in frame.locals {
 663             self.deallocate_local(local.value)?;
 664         }
 665
 666         trace!(
 667             "StackPopCleanup: {:?} StackPopInfo: {:?} cur_unwinding = {:?}",
 668             frame.return_to_block,
 669             stack_pop_info,
 670             cur_unwinding
 671         );
 672         if cur_unwinding {
 673             // Follow the unwind edge.
 674             let unwind = next_block.expect("Encounted StackPopCleanup::None when unwinding!");
 675             self.unwind_to_block(unwind);
 676         } else {
 677             // Follow the normal return edge.
 678             // Validate the return value. Do this after deallocating so that we catch dangling
 679             // references.
 680             if let Some(return_place) = frame.return_place {
 681                 if M::enforce_validity(self) {
 682                     // Data got changed, better make sure it matches the type!
 683                     // It is still possible that the return place held invalid data while
 684                     // the function is running, but that's okay because nobody could have
 685                     // accessed that same data from the "outside" to observe any broken
 686                     // invariant -- that is, unless a function somehow has a ptr to
 687                     // its return place... but the way MIR is currently generated, the
 688                     // return place is always a local and then this cannot happen.
 689                     self.validate_operand(self.place_to_op(return_place)?, vec![], None)?;
 690                 }
 691             } else {
 692                 // Uh, that shouldn't happen... the function did not intend to return
 693                 throw_ub!(Unreachable);
 694             }
 695
 696             // Jump to new block -- *after* validation so that the spans make more sense.
 697             if let Some(ret) = next_block {
 698                 self.return_to_block(ret)?;
 699             }
 700         }
 701
 702         if self.stack.len() > 0 {
 703             info!(
 704                 "CONTINUING({}) {} (unwinding = {})",
 705                 self.cur_frame(),
 706                 self.frame().instance,
 707                 cur_unwinding
 708             );
 709         }
 710
 711         Ok(())
 712     }
 713
 714     /// Mark a storage as live, killing the previous content and returning it.
 715     /// Remember to deallocate that!
 716     pub fn storage_live(
 717         &mut self,
 718         local: mir::Local,
 719     ) -> InterpResult<'tcx, LocalValue<M::PointerTag>> {
 720         assert!(local != mir::RETURN_PLACE, "Cannot make return place live");
 721         trace!("{:?} is now live", local);
 722
 723         let local_val = LocalValue::Uninitialized;
 724         // StorageLive *always* kills the value that's currently stored.
 725         // However, we do not error if the variable already is live;
 726         // see <https://github.com/rust-lang/rust/issues/42371>.
 727         Ok(mem::replace(&mut self.frame_mut().locals[local].value, local_val))
 728     }
 729
 730     /// Returns the old value of the local.
 731     /// Remember to deallocate that!
 732     pub fn storage_dead(&mut self, local: mir::Local) -> LocalValue<M::PointerTag> {
 733         assert!(local != mir::RETURN_PLACE, "Cannot make return place dead");
 734         trace!("{:?} is now dead", local);
 735
 736         mem::replace(&mut self.frame_mut().locals[local].value, LocalValue::Dead)
 737     }
 738
 739     pub(super) fn deallocate_local(
 740         &mut self,
 741         local: LocalValue<M::PointerTag>,
 742     ) -> InterpResult<'tcx> {
 743         // FIXME: should we tell the user that there was a local which was never written to?
 744         if let LocalValue::Live(Operand::Indirect(MemPlace { ptr, .. })) = local {
 745             trace!("deallocating local");
 746             // All locals have a backing allocation, even if the allocation is empty
 747             // due to the local having ZST type.
 748             let ptr = ptr.assert_ptr();
 749             if log_enabled!(::log::Level::Trace) {
 750                 self.memory.dump_alloc(ptr.alloc_id);
 751             }
 752             self.memory.deallocate_local(ptr)?;
 753         };
 754         Ok(())
 755     }
 756
 757     pub(super) fn const_eval(
 758         &self,
 759         gid: GlobalId<'tcx>,
 760     ) -> InterpResult<'tcx, OpTy<'tcx, M::PointerTag>> {
 761         // For statics we pick `ParamEnv::reveal_all`, because statics don't have generics
 762         // and thus don't care about the parameter environment. While we could just use
 763         // `self.param_env`, that would mean we invoke the query to evaluate the static
 764         // with different parameter environments, thus causing the static to be evaluated
 765         // multiple times.
 766         let param_env = if self.tcx.is_static(gid.instance.def_id()) {
 767             ty::ParamEnv::reveal_all()
 768         } else {
 769             self.param_env
 770         };
 771         let val = self.tcx.const_eval(param_env.and(gid))?;
 772         self.eval_const_to_op(val, None)
 773     }
 774
 775     pub fn const_eval_raw(
 776         &self,
 777         gid: GlobalId<'tcx>,
 778     ) -> InterpResult<'tcx, MPlaceTy<'tcx, M::PointerTag>> {
 779         // For statics we pick `ParamEnv::reveal_all`, because statics don't have generics
 780         // and thus don't care about the parameter environment. While we could just use
 781         // `self.param_env`, that would mean we invoke the query to evaluate the static
 782         // with different parameter environments, thus causing the static to be evaluated
 783         // multiple times.
 784         let param_env = if self.tcx.is_static(gid.instance.def_id()) {
 785             ty::ParamEnv::reveal_all()
 786         } else {
 787             self.param_env
 788         };
 789         // We use `const_eval_raw` here, and get an unvalidated result.  That is okay:
 790         // Our result will later be validated anyway, and there seems no good reason
 791         // to have to fail early here.  This is also more consistent with
 792         // `Memory::get_static_alloc` which has to use `const_eval_raw` to avoid cycles.
 793         let val = self.tcx.const_eval_raw(param_env.and(gid))?;
 794         self.raw_const_to_mplace(val)
 795     }
 796
 797     pub fn dump_place(&self, place: Place<M::PointerTag>) {
 798         // Debug output
 799         if !log_enabled!(::log::Level::Trace) {
 800             return;
 801         }
 802         match place {
 803             Place::Local { frame, local } => {
 804                 let mut allocs = Vec::new();
 805                 let mut msg = format!("{:?}", local);
 806                 if frame != self.cur_frame() {
 807                     write!(msg, " ({} frames up)", self.cur_frame() - frame).unwrap();
 808                 }
 809                 write!(msg, ":").unwrap();
 810
 811                 match self.stack[frame].locals[local].value {
 812                     LocalValue::Dead => write!(msg, " is dead").unwrap(),
 813                     LocalValue::Uninitialized => write!(msg, " is uninitialized").unwrap(),
 814                     LocalValue::Live(Operand::Indirect(mplace)) => match mplace.ptr {
 815                         Scalar::Ptr(ptr) => {
 816                             write!(
 817                                 msg,
 818                                 " by align({}){} ref:",
 819                                 mplace.align.bytes(),
 820                                 match mplace.meta {
 821                                     Some(meta) => format!(" meta({:?})", meta),
 822                                     None => String::new(),
 823                                 }
 824                             )
 825                             .unwrap();
 826                             allocs.push(ptr.alloc_id);
 827                         }
 828                         ptr => write!(msg, " by integral ref: {:?}", ptr).unwrap(),
 829                     },
 830                     LocalValue::Live(Operand::Immediate(Immediate::Scalar(val))) => {
 831                         write!(msg, " {:?}", val).unwrap();
 832                         if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val {
 833                             allocs.push(ptr.alloc_id);
 834                         }
 835                     }
 836                     LocalValue::Live(Operand::Immediate(Immediate::ScalarPair(val1, val2))) => {
 837                         write!(msg, " ({:?}, {:?})", val1, val2).unwrap();
 838                         if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val1 {
 839                             allocs.push(ptr.alloc_id);
 840                         }
 841                         if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val2 {
 842                             allocs.push(ptr.alloc_id);
 843                         }
 844                     }
 845                 }
 846
 847                 trace!("{}", msg);
 848                 self.memory.dump_allocs(allocs);
 849             }
 850             Place::Ptr(mplace) => match mplace.ptr {
 851                 Scalar::Ptr(ptr) => {
 852                     trace!("by align({}) ref:", mplace.align.bytes());
 853                     self.memory.dump_alloc(ptr.alloc_id);
 854                 }
 855                 ptr => trace!(" integral by ref: {:?}", ptr),
 856             },
 857         }
 858     }
 859
 860     pub fn generate_stacktrace(&self, explicit_span: Option<Span>) -> Vec<FrameInfo<'tcx>> {
 861         let mut last_span = None;
 862         let mut frames = Vec::new();
 863         for frame in self.stack().iter().rev() {
 864             // make sure we don't emit frames that are duplicates of the previous
 865             if explicit_span == Some(frame.span) {
 866                 last_span = Some(frame.span);
 867                 continue;
 868             }
 869             if let Some(last) = last_span {
 870                 if last == frame.span {
 871                     continue;
 872                 }
 873             } else {
 874                 last_span = Some(frame.span);
 875             }
 876
 877             let lint_root = frame.current_source_info().and_then(|source_info| {
 878                 match &frame.body.source_scopes[source_info.scope].local_data {
 879                     mir::ClearCrossCrate::Set(data) => Some(data.lint_root),
 880                     mir::ClearCrossCrate::Clear => None,
 881                 }
 882             });
 883
 884             frames.push(FrameInfo { call_site: frame.span, instance: frame.instance, lint_root });
 885         }
 886         trace!("generate stacktrace: {:#?}, {:?}", frames, explicit_span);
 887         frames
 888     }
 889 }
 890
 891 impl<'ctx, 'mir, 'tcx, Tag, Extra> HashStable<StableHashingContext<'ctx>>
 892     for Frame<'mir, 'tcx, Tag, Extra>
 893 where
 894     Extra: HashStable<StableHashingContext<'ctx>>,
 895     Tag: HashStable<StableHashingContext<'ctx>>,
 896 {
 897     fn hash_stable(&self, hcx: &mut StableHashingContext<'ctx>, hasher: &mut StableHasher) {
 898         self.body.hash_stable(hcx, hasher);
 899         self.instance.hash_stable(hcx, hasher);
 900         self.span.hash_stable(hcx, hasher);
 901         self.return_to_block.hash_stable(hcx, hasher);
 902         self.return_place.as_ref().map(|r| &**r).hash_stable(hcx, hasher);
 903         self.locals.hash_stable(hcx, hasher);
 904         self.block.hash_stable(hcx, hasher);
 905         self.stmt.hash_stable(hcx, hasher);
 906         self.extra.hash_stable(hcx, hasher);
 907     }
 908 }