src/librustc_mir/interpret/eval_context.rs

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