src/librustc_mir/interpret/eval_context.rs

   1 use std::fmt::Write;
   2 use std::hash::{Hash, Hasher};
   3 use std::mem;
   4
   5 use rustc::hir::def_id::DefId;
   6 use rustc::hir::def::Def;
   7 use rustc::hir::map::definitions::DefPathData;
   8 use rustc::mir;
   9 use rustc::ty::layout::{self, Size, Align, HasDataLayout, IntegerExt, LayoutOf, TyLayout, Primitive};
  10 use rustc::ty::subst::{Subst, Substs};
  11 use rustc::ty::{self, Ty, TyCtxt, TypeAndMut};
  12 use rustc::ty::query::TyCtxtAt;
  13 use rustc_data_structures::fx::{FxHashSet, FxHasher};
  14 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  15 use rustc::mir::interpret::{
  16     GlobalId, Value, Scalar, FrameInfo, AllocType,
  17     EvalResult, EvalErrorKind, Pointer, ConstValue,
  18     ScalarMaybeUndef,
  19 };
  20
  21 use syntax::codemap::{self, Span};
  22 use syntax::ast::Mutability;
  23
  24 use super::{Place, PlaceExtra, Memory,
  25             HasMemory, MemoryKind,
  26             Machine};
  27
  28 macro_rules! validation_failure{
  29     ($what:expr, $where:expr, $details:expr) => {{
  30         let where_ = if $where.is_empty() {
  31             String::new()
  32         } else {
  33             format!(" at {}", $where)
  34         };
  35         err!(ValidationFailure(format!(
  36             "encountered {}{}, but expected {}",
  37             $what, where_, $details,
  38         )))
  39     }};
  40     ($what:expr, $where:expr) => {{
  41         let where_ = if $where.is_empty() {
  42             String::new()
  43         } else {
  44             format!(" at {}", $where)
  45         };
  46         err!(ValidationFailure(format!(
  47             "encountered {}{}",
  48             $what, where_,
  49         )))
  50     }};
  51 }
  52
  53 pub struct EvalContext<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'mir, 'tcx>> {
  54     /// Stores the `Machine` instance.
  55     pub machine: M,
  56
  57     /// The results of the type checker, from rustc.
  58     pub tcx: TyCtxtAt<'a, 'tcx, 'tcx>,
  59
  60     /// Bounds in scope for polymorphic evaluations.
  61     pub param_env: ty::ParamEnv<'tcx>,
  62
  63     /// The virtual memory system.
  64     pub memory: Memory<'a, 'mir, 'tcx, M>,
  65
  66     /// The virtual call stack.
  67     pub(crate) stack: Vec<Frame<'mir, 'tcx>>,
  68
  69     /// The maximum number of stack frames allowed
  70     pub(crate) stack_limit: usize,
  71
  72     /// When this value is negative, it indicates the number of interpreter
  73     /// steps *until* the loop detector is enabled. When it is positive, it is
  74     /// the number of steps after the detector has been enabled modulo the loop
  75     /// detector period.
  76     pub(crate) steps_since_detector_enabled: isize,
  77
  78     pub(crate) loop_detector: InfiniteLoopDetector<'a, 'mir, 'tcx, M>,
  79 }
  80
  81 /// A stack frame.
  82 #[derive(Clone)]
  83 pub struct Frame<'mir, 'tcx: 'mir> {
  84     ////////////////////////////////////////////////////////////////////////////////
  85     // Function and callsite information
  86     ////////////////////////////////////////////////////////////////////////////////
  87     /// The MIR for the function called on this frame.
  88     pub mir: &'mir mir::Mir<'tcx>,
  89
  90     /// The def_id and substs of the current function
  91     pub instance: ty::Instance<'tcx>,
  92
  93     /// The span of the call site.
  94     pub span: codemap::Span,
  95
  96     ////////////////////////////////////////////////////////////////////////////////
  97     // Return place and locals
  98     ////////////////////////////////////////////////////////////////////////////////
  99     /// The block to return to when returning from the current stack frame
 100     pub return_to_block: StackPopCleanup,
 101
 102     /// The location where the result of the current stack frame should be written to.
 103     pub return_place: Place,
 104
 105     /// The list of locals for this stack frame, stored in order as
 106     /// `[return_ptr, arguments..., variables..., temporaries...]`. The locals are stored as `Option<Value>`s.
 107     /// `None` represents a local that is currently dead, while a live local
 108     /// can either directly contain `Scalar` or refer to some part of an `Allocation`.
 109     pub locals: IndexVec<mir::Local, LocalValue>,
 110
 111     ////////////////////////////////////////////////////////////////////////////////
 112     // Current position within the function
 113     ////////////////////////////////////////////////////////////////////////////////
 114     /// The block that is currently executed (or will be executed after the above call stacks
 115     /// return).
 116     pub block: mir::BasicBlock,
 117
 118     /// The index of the currently evaluated statement.
 119     pub stmt: usize,
 120 }
 121
 122 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 123 pub enum LocalValue {
 124     Dead,
 125     Live(Value),
 126 }
 127
 128 impl LocalValue {
 129     pub fn access(self) -> EvalResult<'static, Value> {
 130         match self {
 131             LocalValue::Dead => err!(DeadLocal),
 132             LocalValue::Live(val) => Ok(val),
 133         }
 134     }
 135 }
 136
 137 impl<'mir, 'tcx: 'mir> Eq for Frame<'mir, 'tcx> {}
 138
 139 impl<'mir, 'tcx: 'mir> PartialEq for Frame<'mir, 'tcx> {
 140     fn eq(&self, other: &Self) -> bool {
 141         let Frame {
 142             mir: _,
 143             instance,
 144             span: _,
 145             return_to_block,
 146             return_place,
 147             locals,
 148             block,
 149             stmt,
 150         } = self;
 151
 152         // Some of these are constant during evaluation, but are included
 153         // anyways for correctness.
 154         *instance == other.instance
 155             && *return_to_block == other.return_to_block
 156             && *return_place == other.return_place
 157             && *locals == other.locals
 158             && *block == other.block
 159             && *stmt == other.stmt
 160     }
 161 }
 162
 163 impl<'mir, 'tcx: 'mir> Hash for Frame<'mir, 'tcx> {
 164     fn hash<H: Hasher>(&self, state: &mut H) {
 165         let Frame {
 166             mir: _,
 167             instance,
 168             span: _,
 169             return_to_block,
 170             return_place,
 171             locals,
 172             block,
 173             stmt,
 174         } = self;
 175
 176         instance.hash(state);
 177         return_to_block.hash(state);
 178         return_place.hash(state);
 179         locals.hash(state);
 180         block.hash(state);
 181         stmt.hash(state);
 182     }
 183 }
 184
 185 /// The virtual machine state during const-evaluation at a given point in time.
 186 type EvalSnapshot<'a, 'mir, 'tcx, M>
 187     = (M, Vec<Frame<'mir, 'tcx>>, Memory<'a, 'mir, 'tcx, M>);
 188
 189 pub(crate) struct InfiniteLoopDetector<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'mir, 'tcx>> {
 190     /// The set of all `EvalSnapshot` *hashes* observed by this detector.
 191     ///
 192     /// When a collision occurs in this table, we store the full snapshot in
 193     /// `snapshots`.
 194     hashes: FxHashSet<u64>,
 195
 196     /// The set of all `EvalSnapshot`s observed by this detector.
 197     ///
 198     /// An `EvalSnapshot` will only be fully cloned once it has caused a
 199     /// collision in `hashes`. As a result, the detector must observe at least
 200     /// *two* full cycles of an infinite loop before it triggers.
 201     snapshots: FxHashSet<EvalSnapshot<'a, 'mir, 'tcx, M>>,
 202 }
 203
 204 impl<'a, 'mir, 'tcx, M> Default for InfiniteLoopDetector<'a, 'mir, 'tcx, M>
 205     where M: Machine<'mir, 'tcx>,
 206           'tcx: 'a + 'mir,
 207 {
 208     fn default() -> Self {
 209         InfiniteLoopDetector {
 210             hashes: FxHashSet::default(),
 211             snapshots: FxHashSet::default(),
 212         }
 213     }
 214 }
 215
 216 impl<'a, 'mir, 'tcx, M> InfiniteLoopDetector<'a, 'mir, 'tcx, M>
 217     where M: Machine<'mir, 'tcx>,
 218           'tcx: 'a + 'mir,
 219 {
 220     /// Returns `true` if the loop detector has not yet observed a snapshot.
 221     pub fn is_empty(&self) -> bool {
 222         self.hashes.is_empty()
 223     }
 224
 225     pub fn observe_and_analyze(
 226         &mut self,
 227         machine: &M,
 228         stack: &Vec<Frame<'mir, 'tcx>>,
 229         memory: &Memory<'a, 'mir, 'tcx, M>,
 230     ) -> EvalResult<'tcx, ()> {
 231         let snapshot = (machine, stack, memory);
 232
 233         let mut fx = FxHasher::default();
 234         snapshot.hash(&mut fx);
 235         let hash = fx.finish();
 236
 237         if self.hashes.insert(hash) {
 238             // No collision
 239             return Ok(())
 240         }
 241
 242         if self.snapshots.insert((machine.clone(), stack.clone(), memory.clone())) {
 243             // Spurious collision or first cycle
 244             return Ok(())
 245         }
 246
 247         // Second cycle
 248         Err(EvalErrorKind::InfiniteLoop.into())
 249     }
 250 }
 251
 252 #[derive(Clone, Debug, Eq, PartialEq, Hash)]
 253 pub enum StackPopCleanup {
 254     /// The stackframe existed to compute the initial value of a static/constant, make sure it
 255     /// isn't modifyable afterwards in case of constants.
 256     /// In case of `static mut`, mark the memory to ensure it's never marked as immutable through
 257     /// references or deallocated
 258     MarkStatic(Mutability),
 259     /// A regular stackframe added due to a function call will need to get forwarded to the next
 260     /// block
 261     Goto(mir::BasicBlock),
 262     /// The main function and diverging functions have nowhere to return to
 263     None,
 264 }
 265
 266 #[derive(Copy, Clone, Debug)]
 267 pub struct TyAndPacked<'tcx> {
 268     pub ty: Ty<'tcx>,
 269     pub packed: bool,
 270 }
 271
 272 #[derive(Copy, Clone, Debug)]
 273 pub struct ValTy<'tcx> {
 274     pub value: Value,
 275     pub ty: Ty<'tcx>,
 276 }
 277
 278 impl<'tcx> ::std::ops::Deref for ValTy<'tcx> {
 279     type Target = Value;
 280     fn deref(&self) -> &Value {
 281         &self.value
 282     }
 283 }
 284
 285 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> HasDataLayout for &'a EvalContext<'a, 'mir, 'tcx, M> {
 286     #[inline]
 287     fn data_layout(&self) -> &layout::TargetDataLayout {
 288         &self.tcx.data_layout
 289     }
 290 }
 291
 292 impl<'c, 'b, 'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> HasDataLayout
 293     for &'c &'b mut EvalContext<'a, 'mir, 'tcx, M> {
 294     #[inline]
 295     fn data_layout(&self) -> &layout::TargetDataLayout {
 296         &self.tcx.data_layout
 297     }
 298 }
 299
 300 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> layout::HasTyCtxt<'tcx> for &'a EvalContext<'a, 'mir, 'tcx, M> {
 301     #[inline]
 302     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> {
 303         *self.tcx
 304     }
 305 }
 306
 307 impl<'c, 'b, 'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> layout::HasTyCtxt<'tcx>
 308     for &'c &'b mut EvalContext<'a, 'mir, 'tcx, M> {
 309     #[inline]
 310     fn tcx<'d>(&'d self) -> TyCtxt<'d, 'tcx, 'tcx> {
 311         *self.tcx
 312     }
 313 }
 314
 315 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> LayoutOf for &'a EvalContext<'a, 'mir, 'tcx, M> {
 316     type Ty = Ty<'tcx>;
 317     type TyLayout = EvalResult<'tcx, TyLayout<'tcx>>;
 318
 319     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
 320         self.tcx.layout_of(self.param_env.and(ty))
 321             .map_err(|layout| EvalErrorKind::Layout(layout).into())
 322     }
 323 }
 324
 325 impl<'c, 'b, 'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> LayoutOf
 326     for &'c &'b mut EvalContext<'a, 'mir, 'tcx, M> {
 327     type Ty = Ty<'tcx>;
 328     type TyLayout = EvalResult<'tcx, TyLayout<'tcx>>;
 329
 330     #[inline]
 331     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
 332         (&**self).layout_of(ty)
 333     }
 334 }
 335
 336 const STEPS_UNTIL_DETECTOR_ENABLED: isize = 1_000_000;
 337
 338 impl<'a, 'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> EvalContext<'a, 'mir, 'tcx, M> {
 339     pub fn new(
 340         tcx: TyCtxtAt<'a, 'tcx, 'tcx>,
 341         param_env: ty::ParamEnv<'tcx>,
 342         machine: M,
 343         memory_data: M::MemoryData,
 344     ) -> Self {
 345         EvalContext {
 346             machine,
 347             tcx,
 348             param_env,
 349             memory: Memory::new(tcx, memory_data),
 350             stack: Vec::new(),
 351             stack_limit: tcx.sess.const_eval_stack_frame_limit,
 352             loop_detector: Default::default(),
 353             steps_since_detector_enabled: -STEPS_UNTIL_DETECTOR_ENABLED,
 354         }
 355     }
 356
 357     pub(crate) fn with_fresh_body<F: FnOnce(&mut Self) -> R, R>(&mut self, f: F) -> R {
 358         let stack = mem::replace(&mut self.stack, Vec::new());
 359         let steps = mem::replace(&mut self.steps_since_detector_enabled, -STEPS_UNTIL_DETECTOR_ENABLED);
 360         let r = f(self);
 361         self.stack = stack;
 362         self.steps_since_detector_enabled = steps;
 363         r
 364     }
 365
 366     pub fn alloc_ptr(&mut self, layout: TyLayout<'tcx>) -> EvalResult<'tcx, Pointer> {
 367         assert!(!layout.is_unsized(), "cannot alloc memory for unsized type");
 368
 369         self.memory.allocate(layout.size, layout.align, MemoryKind::Stack)
 370     }
 371
 372     pub fn memory(&self) -> &Memory<'a, 'mir, 'tcx, M> {
 373         &self.memory
 374     }
 375
 376     pub fn memory_mut(&mut self) -> &mut Memory<'a, 'mir, 'tcx, M> {
 377         &mut self.memory
 378     }
 379
 380     pub fn stack(&self) -> &[Frame<'mir, 'tcx>] {
 381         &self.stack
 382     }
 383
 384     #[inline]
 385     pub fn cur_frame(&self) -> usize {
 386         assert!(self.stack.len() > 0);
 387         self.stack.len() - 1
 388     }
 389
 390     pub fn str_to_value(&mut self, s: &str) -> EvalResult<'tcx, Value> {
 391         let ptr = self.memory.allocate_bytes(s.as_bytes());
 392         Ok(Scalar::Ptr(ptr).to_value_with_len(s.len() as u64, self.tcx.tcx))
 393     }
 394
 395     pub fn const_to_value(
 396         &mut self,
 397         val: ConstValue<'tcx>,
 398     ) -> EvalResult<'tcx, Value> {
 399         match val {
 400             ConstValue::Unevaluated(def_id, substs) => {
 401                 let instance = self.resolve(def_id, substs)?;
 402                 self.read_global_as_value(GlobalId {
 403                     instance,
 404                     promoted: None,
 405                 })
 406             }
 407             ConstValue::ByRef(alloc, offset) => {
 408                 // FIXME: Allocate new AllocId for all constants inside
 409                 let id = self.memory.allocate_value(alloc.clone(), MemoryKind::Stack)?;
 410                 Ok(Value::ByRef(Pointer::new(id, offset).into(), alloc.align))
 411             },
 412             ConstValue::ScalarPair(a, b) => Ok(Value::ScalarPair(a.into(), b.into())),
 413             ConstValue::Scalar(val) => Ok(Value::Scalar(val.into())),
 414         }
 415     }
 416
 417     pub(super) fn resolve(&self, def_id: DefId, substs: &'tcx Substs<'tcx>) -> EvalResult<'tcx, ty::Instance<'tcx>> {
 418         trace!("resolve: {:?}, {:#?}", def_id, substs);
 419         trace!("substs: {:#?}", self.substs());
 420         trace!("param_env: {:#?}", self.param_env);
 421         let substs = self.tcx.subst_and_normalize_erasing_regions(
 422             self.substs(),
 423             self.param_env,
 424             &substs,
 425         );
 426         ty::Instance::resolve(
 427             *self.tcx,
 428             self.param_env,
 429             def_id,
 430             substs,
 431         ).ok_or_else(|| EvalErrorKind::TooGeneric.into())
 432     }
 433
 434     pub(super) fn type_is_sized(&self, ty: Ty<'tcx>) -> bool {
 435         ty.is_sized(self.tcx, self.param_env)
 436     }
 437
 438     pub fn load_mir(
 439         &self,
 440         instance: ty::InstanceDef<'tcx>,
 441     ) -> EvalResult<'tcx, &'tcx mir::Mir<'tcx>> {
 442         // do not continue if typeck errors occurred (can only occur in local crate)
 443         let did = instance.def_id();
 444         if did.is_local() && self.tcx.has_typeck_tables(did) && self.tcx.typeck_tables_of(did).tainted_by_errors {
 445             return err!(TypeckError);
 446         }
 447         trace!("load mir {:?}", instance);
 448         match instance {
 449             ty::InstanceDef::Item(def_id) => {
 450                 self.tcx.maybe_optimized_mir(def_id).ok_or_else(||
 451                     EvalErrorKind::NoMirFor(self.tcx.item_path_str(def_id)).into()
 452                 )
 453             }
 454             _ => Ok(self.tcx.instance_mir(instance)),
 455         }
 456     }
 457
 458     pub fn monomorphize(&self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
 459         // miri doesn't care about lifetimes, and will choke on some crazy ones
 460         // let's simply get rid of them
 461         let substituted = ty.subst(*self.tcx, substs);
 462         self.tcx.normalize_erasing_regions(ty::ParamEnv::reveal_all(), substituted)
 463     }
 464
 465     /// Return the size and aligment of the value at the given type.
 466     /// Note that the value does not matter if the type is sized. For unsized types,
 467     /// the value has to be a fat pointer, and we only care about the "extra" data in it.
 468     pub fn size_and_align_of_dst(
 469         &mut self,
 470         ty: Ty<'tcx>,
 471         value: Value,
 472     ) -> EvalResult<'tcx, (Size, Align)> {
 473         let layout = self.layout_of(ty)?;
 474         if !layout.is_unsized() {
 475             Ok(layout.size_and_align())
 476         } else {
 477             match ty.sty {
 478                 ty::TyAdt(..) | ty::TyTuple(..) => {
 479                     // First get the size of all statically known fields.
 480                     // Don't use type_of::sizing_type_of because that expects t to be sized,
 481                     // and it also rounds up to alignment, which we want to avoid,
 482                     // as the unsized field's alignment could be smaller.
 483                     assert!(!ty.is_simd());
 484                     debug!("DST {} layout: {:?}", ty, layout);
 485
 486                     let sized_size = layout.fields.offset(layout.fields.count() - 1);
 487                     let sized_align = layout.align;
 488                     debug!(
 489                         "DST {} statically sized prefix size: {:?} align: {:?}",
 490                         ty,
 491                         sized_size,
 492                         sized_align
 493                     );
 494
 495                     // Recurse to get the size of the dynamically sized field (must be
 496                     // the last field).
 497                     let field_ty = layout.field(&self, layout.fields.count() - 1)?.ty;
 498                     let (unsized_size, unsized_align) =
 499                         self.size_and_align_of_dst(field_ty, value)?;
 500
 501                     // FIXME (#26403, #27023): We should be adding padding
 502                     // to `sized_size` (to accommodate the `unsized_align`
 503                     // required of the unsized field that follows) before
 504                     // summing it with `sized_size`. (Note that since #26403
 505                     // is unfixed, we do not yet add the necessary padding
 506                     // here. But this is where the add would go.)
 507
 508                     // Return the sum of sizes and max of aligns.
 509                     let size = sized_size + unsized_size;
 510
 511                     // Choose max of two known alignments (combined value must
 512                     // be aligned according to more restrictive of the two).
 513                     let align = sized_align.max(unsized_align);
 514
 515                     // Issue #27023: must add any necessary padding to `size`
 516                     // (to make it a multiple of `align`) before returning it.
 517                     //
 518                     // Namely, the returned size should be, in C notation:
 519                     //
 520                     //   `size + ((size & (align-1)) ? align : 0)`
 521                     //
 522                     // emulated via the semi-standard fast bit trick:
 523                     //
 524                     //   `(size + (align-1)) & -align`
 525
 526                     Ok((size.abi_align(align), align))
 527                 }
 528                 ty::TyDynamic(..) => {
 529                     let (_, vtable) = self.into_ptr_vtable_pair(value)?;
 530                     // the second entry in the vtable is the dynamic size of the object.
 531                     self.read_size_and_align_from_vtable(vtable)
 532                 }
 533
 534                 ty::TySlice(_) | ty::TyStr => {
 535                     let (elem_size, align) = layout.field(&self, 0)?.size_and_align();
 536                     let (_, len) = self.into_slice(value)?;
 537                     Ok((elem_size * len, align))
 538                 }
 539
 540                 _ => bug!("size_of_val::<{:?}>", ty),
 541             }
 542         }
 543     }
 544
 545     pub fn push_stack_frame(
 546         &mut self,
 547         instance: ty::Instance<'tcx>,
 548         span: codemap::Span,
 549         mir: &'mir mir::Mir<'tcx>,
 550         return_place: Place,
 551         return_to_block: StackPopCleanup,
 552     ) -> EvalResult<'tcx> {
 553         ::log_settings::settings().indentation += 1;
 554
 555         // first push a stack frame so we have access to the local substs
 556         self.stack.push(Frame {
 557             mir,
 558             block: mir::START_BLOCK,
 559             return_to_block,
 560             return_place,
 561             // empty local array, we fill it in below, after we are inside the stack frame and
 562             // all methods actually know about the frame
 563             locals: IndexVec::new(),
 564             span,
 565             instance,
 566             stmt: 0,
 567         });
 568
 569         // don't allocate at all for trivial constants
 570         if mir.local_decls.len() > 1 {
 571             let mut locals = IndexVec::from_elem(LocalValue::Dead, &mir.local_decls);
 572             for (local, decl) in locals.iter_mut().zip(mir.local_decls.iter()) {
 573                 *local = LocalValue::Live(self.init_value(decl.ty)?);
 574             }
 575             match self.tcx.describe_def(instance.def_id()) {
 576                 // statics and constants don't have `Storage*` statements, no need to look for them
 577                 Some(Def::Static(..)) | Some(Def::Const(..)) | Some(Def::AssociatedConst(..)) => {},
 578                 _ => {
 579                     trace!("push_stack_frame: {:?}: num_bbs: {}", span, mir.basic_blocks().len());
 580                     for block in mir.basic_blocks() {
 581                         for stmt in block.statements.iter() {
 582                             use rustc::mir::StatementKind::{StorageDead, StorageLive};
 583                             match stmt.kind {
 584                                 StorageLive(local) |
 585                                 StorageDead(local) => locals[local] = LocalValue::Dead,
 586                                 _ => {}
 587                             }
 588                         }
 589                     }
 590                 },
 591             }
 592             self.frame_mut().locals = locals;
 593         }
 594
 595         self.memory.cur_frame = self.cur_frame();
 596
 597         if self.stack.len() > self.stack_limit {
 598             err!(StackFrameLimitReached)
 599         } else {
 600             Ok(())
 601         }
 602     }
 603
 604     pub(super) fn pop_stack_frame(&mut self) -> EvalResult<'tcx> {
 605         ::log_settings::settings().indentation -= 1;
 606         M::end_region(self, None)?;
 607         let frame = self.stack.pop().expect(
 608             "tried to pop a stack frame, but there were none",
 609         );
 610         if !self.stack.is_empty() {
 611             // TODO: Is this the correct time to start considering these accesses as originating from the returned-to stack frame?
 612             self.memory.cur_frame = self.cur_frame();
 613         }
 614         match frame.return_to_block {
 615             StackPopCleanup::MarkStatic(mutable) => {
 616                 if let Place::Ptr { ptr, .. } = frame.return_place {
 617                     // FIXME: to_ptr()? might be too extreme here, static zsts might reach this under certain conditions
 618                     self.memory.mark_static_initialized(
 619                         ptr.read()?.to_ptr()?.alloc_id,
 620                         mutable,
 621                     )?
 622                 } else {
 623                     bug!("StackPopCleanup::MarkStatic on: {:?}", frame.return_place);
 624                 }
 625             }
 626             StackPopCleanup::Goto(target) => self.goto_block(target),
 627             StackPopCleanup::None => {}
 628         }
 629         // deallocate all locals that are backed by an allocation
 630         for local in frame.locals {
 631             self.deallocate_local(local)?;
 632         }
 633
 634         Ok(())
 635     }
 636
 637     pub fn deallocate_local(&mut self, local: LocalValue) -> EvalResult<'tcx> {
 638         // FIXME: should we tell the user that there was a local which was never written to?
 639         if let LocalValue::Live(Value::ByRef(ptr, _align)) = local {
 640             trace!("deallocating local");
 641             let ptr = ptr.to_ptr()?;
 642             self.memory.dump_alloc(ptr.alloc_id);
 643             self.memory.deallocate_local(ptr)?;
 644         };
 645         Ok(())
 646     }
 647
 648     /// Evaluate an assignment statement.
 649     ///
 650     /// There is no separate `eval_rvalue` function. Instead, the code for handling each rvalue
 651     /// type writes its results directly into the memory specified by the place.
 652     pub(super) fn eval_rvalue_into_place(
 653         &mut self,
 654         rvalue: &mir::Rvalue<'tcx>,
 655         place: &mir::Place<'tcx>,
 656     ) -> EvalResult<'tcx> {
 657         let dest = self.eval_place(place)?;
 658         let dest_ty = self.place_ty(place);
 659         let dest_layout = self.layout_of(dest_ty)?;
 660
 661         use rustc::mir::Rvalue::*;
 662         match *rvalue {
 663             Use(ref operand) => {
 664                 let value = self.eval_operand(operand)?.value;
 665                 let valty = ValTy {
 666                     value,
 667                     ty: dest_ty,
 668                 };
 669                 self.write_value(valty, dest)?;
 670             }
 671
 672             BinaryOp(bin_op, ref left, ref right) => {
 673                 let left = self.eval_operand(left)?;
 674                 let right = self.eval_operand(right)?;
 675                 self.intrinsic_overflowing(
 676                     bin_op,
 677                     left,
 678                     right,
 679                     dest,
 680                     dest_ty,
 681                 )?;
 682             }
 683
 684             CheckedBinaryOp(bin_op, ref left, ref right) => {
 685                 let left = self.eval_operand(left)?;
 686                 let right = self.eval_operand(right)?;
 687                 self.intrinsic_with_overflow(
 688                     bin_op,
 689                     left,
 690                     right,
 691                     dest,
 692                     dest_ty,
 693                 )?;
 694             }
 695
 696             UnaryOp(un_op, ref operand) => {
 697                 let val = self.eval_operand_to_scalar(operand)?;
 698                 let val = self.unary_op(un_op, val, dest_layout)?;
 699                 self.write_scalar(
 700                     dest,
 701                     val,
 702                     dest_ty,
 703                 )?;
 704             }
 705
 706             Aggregate(ref kind, ref operands) => {
 707                 let (dest, active_field_index) = match **kind {
 708                     mir::AggregateKind::Adt(adt_def, variant_index, _, active_field_index) => {
 709                         self.write_discriminant_value(dest_ty, dest, variant_index)?;
 710                         if adt_def.is_enum() {
 711                             (self.place_downcast(dest, variant_index)?, active_field_index)
 712                         } else {
 713                             (dest, active_field_index)
 714                         }
 715                     }
 716                     _ => (dest, None)
 717                 };
 718
 719                 let layout = self.layout_of(dest_ty)?;
 720                 for (i, operand) in operands.iter().enumerate() {
 721                     let value = self.eval_operand(operand)?;
 722                     // Ignore zero-sized fields.
 723                     if !self.layout_of(value.ty)?.is_zst() {
 724                         let field_index = active_field_index.unwrap_or(i);
 725                         let (field_dest, _) = self.place_field(dest, mir::Field::new(field_index), layout)?;
 726                         self.write_value(value, field_dest)?;
 727                     }
 728                 }
 729             }
 730
 731             Repeat(ref operand, _) => {
 732                 let (elem_ty, length) = match dest_ty.sty {
 733                     ty::TyArray(elem_ty, n) => (elem_ty, n.unwrap_usize(self.tcx.tcx)),
 734                     _ => {
 735                         bug!(
 736                             "tried to assign array-repeat to non-array type {:?}",
 737                             dest_ty
 738                         )
 739                     }
 740                 };
 741                 let elem_size = self.layout_of(elem_ty)?.size;
 742                 let value = self.eval_operand(operand)?.value;
 743
 744                 let (dest, dest_align) = self.force_allocation(dest)?.to_ptr_align();
 745
 746                 if length > 0 {
 747                     let dest = dest.read()?;
 748                     //write the first value
 749                     self.write_value_to_ptr(value, dest, dest_align, elem_ty)?;
 750
 751                     if length > 1 {
 752                         let rest = dest.ptr_offset(elem_size * 1 as u64, &self)?;
 753                         self.memory.copy_repeatedly(dest, dest_align, rest, dest_align, elem_size, length - 1, false)?;
 754                     }
 755                 }
 756             }
 757
 758             Len(ref place) => {
 759                 // FIXME(CTFE): don't allow computing the length of arrays in const eval
 760                 let src = self.eval_place(place)?;
 761                 let ty = self.place_ty(place);
 762                 let (_, len) = src.elem_ty_and_len(ty, self.tcx.tcx);
 763                 let size = self.memory.pointer_size().bytes() as u8;
 764                 self.write_scalar(
 765                     dest,
 766                     Scalar::Bits {
 767                         bits: len as u128,
 768                         size,
 769                     },
 770                     dest_ty,
 771                 )?;
 772             }
 773
 774             Ref(_, _, ref place) => {
 775                 let src = self.eval_place(place)?;
 776                 // We ignore the alignment of the place here -- special handling for packed structs ends
 777                 // at the `&` operator.
 778                 let (ptr, _align, extra) = self.force_allocation(src)?.to_ptr_align_extra();
 779
 780                 let val = match extra {
 781                     PlaceExtra::None => Value::Scalar(ptr),
 782                     PlaceExtra::Length(len) => ptr.to_value_with_len(len, self.tcx.tcx),
 783                     PlaceExtra::Vtable(vtable) => ptr.to_value_with_vtable(vtable),
 784                     PlaceExtra::DowncastVariant(..) => {
 785                         bug!("attempted to take a reference to an enum downcast place")
 786                     }
 787                 };
 788                 let valty = ValTy {
 789                     value: val,
 790                     ty: dest_ty,
 791                 };
 792                 self.write_value(valty, dest)?;
 793             }
 794
 795             NullaryOp(mir::NullOp::Box, ty) => {
 796                 let ty = self.monomorphize(ty, self.substs());
 797                 M::box_alloc(self, ty, dest)?;
 798             }
 799
 800             NullaryOp(mir::NullOp::SizeOf, ty) => {
 801                 let ty = self.monomorphize(ty, self.substs());
 802                 let layout = self.layout_of(ty)?;
 803                 assert!(!layout.is_unsized(),
 804                         "SizeOf nullary MIR operator called for unsized type");
 805                 let size = self.memory.pointer_size().bytes() as u8;
 806                 self.write_scalar(
 807                     dest,
 808                     Scalar::Bits {
 809                         bits: layout.size.bytes() as u128,
 810                         size,
 811                     },
 812                     dest_ty,
 813                 )?;
 814             }
 815
 816             Cast(kind, ref operand, cast_ty) => {
 817                 debug_assert_eq!(self.monomorphize(cast_ty, self.substs()), dest_ty);
 818                 let src = self.eval_operand(operand)?;
 819                 self.cast(src, kind, dest_ty, dest)?;
 820             }
 821
 822             Discriminant(ref place) => {
 823                 let ty = self.place_ty(place);
 824                 let layout = self.layout_of(ty)?;
 825                 let place = self.eval_place(place)?;
 826                 let discr_val = self.read_discriminant_value(place, layout)?;
 827                 let size = self.layout_of(dest_ty).unwrap().size.bytes() as u8;
 828                 self.write_scalar(dest, Scalar::Bits {
 829                     bits: discr_val,
 830                     size,
 831                 }, dest_ty)?;
 832             }
 833         }
 834
 835         self.dump_local(dest);
 836
 837         Ok(())
 838     }
 839
 840     pub(super) fn type_is_fat_ptr(&self, ty: Ty<'tcx>) -> bool {
 841         match ty.sty {
 842             ty::TyRawPtr(ty::TypeAndMut { ty, .. }) |
 843             ty::TyRef(_, ty, _) => !self.type_is_sized(ty),
 844             ty::TyAdt(def, _) if def.is_box() => !self.type_is_sized(ty.boxed_ty()),
 845             _ => false,
 846         }
 847     }
 848
 849     pub(super) fn eval_operand_to_scalar(
 850         &mut self,
 851         op: &mir::Operand<'tcx>,
 852     ) -> EvalResult<'tcx, Scalar> {
 853         let valty = self.eval_operand(op)?;
 854         self.value_to_scalar(valty)
 855     }
 856
 857     pub(crate) fn operands_to_args(
 858         &mut self,
 859         ops: &[mir::Operand<'tcx>],
 860     ) -> EvalResult<'tcx, Vec<ValTy<'tcx>>> {
 861         ops.into_iter()
 862             .map(|op| self.eval_operand(op))
 863             .collect()
 864     }
 865
 866     pub fn eval_operand(&mut self, op: &mir::Operand<'tcx>) -> EvalResult<'tcx, ValTy<'tcx>> {
 867         use rustc::mir::Operand::*;
 868         let ty = self.monomorphize(op.ty(self.mir(), *self.tcx), self.substs());
 869         match *op {
 870             // FIXME: do some more logic on `move` to invalidate the old location
 871             Copy(ref place) |
 872             Move(ref place) => {
 873                 Ok(ValTy {
 874                     value: self.eval_and_read_place(place)?,
 875                     ty
 876                 })
 877             },
 878
 879             Constant(ref constant) => {
 880                 let value = self.const_to_value(constant.literal.val)?;
 881
 882                 Ok(ValTy {
 883                     value,
 884                     ty,
 885                 })
 886             }
 887         }
 888     }
 889
 890     /// reads a tag and produces the corresponding variant index
 891     pub fn read_discriminant_as_variant_index(
 892         &self,
 893         place: Place,
 894         layout: TyLayout<'tcx>,
 895     ) -> EvalResult<'tcx, usize> {
 896         match layout.variants {
 897             ty::layout::Variants::Single { index } => Ok(index),
 898             ty::layout::Variants::Tagged { .. } => {
 899                 let discr_val = self.read_discriminant_value(place, layout)?;
 900                 layout
 901                     .ty
 902                     .ty_adt_def()
 903                     .expect("tagged layout for non adt")
 904                     .discriminants(self.tcx.tcx)
 905                     .position(|var| var.val == discr_val)
 906                     .ok_or_else(|| EvalErrorKind::InvalidDiscriminant.into())
 907             }
 908             ty::layout::Variants::NicheFilling { .. } => {
 909                 let discr_val = self.read_discriminant_value(place, layout)?;
 910                 assert_eq!(discr_val as usize as u128, discr_val);
 911                 Ok(discr_val as usize)
 912             },
 913         }
 914     }
 915
 916     pub fn read_discriminant_value(
 917         &self,
 918         place: Place,
 919         layout: TyLayout<'tcx>,
 920     ) -> EvalResult<'tcx, u128> {
 921         trace!("read_discriminant_value {:#?}", layout);
 922         if layout.abi == layout::Abi::Uninhabited {
 923             return Ok(0);
 924         }
 925
 926         match layout.variants {
 927             layout::Variants::Single { index } => {
 928                 let discr_val = layout.ty.ty_adt_def().map_or(
 929                     index as u128,
 930                     |def| def.discriminant_for_variant(*self.tcx, index).val);
 931                 return Ok(discr_val);
 932             }
 933             layout::Variants::Tagged { .. } |
 934             layout::Variants::NicheFilling { .. } => {},
 935         }
 936         let discr_place_val = self.read_place(place)?;
 937         let (discr_val, discr) = self.read_field(discr_place_val, None, mir::Field::new(0), layout)?;
 938         trace!("discr value: {:?}, {:?}", discr_val, discr);
 939         let raw_discr = self.value_to_scalar(ValTy {
 940             value: discr_val,
 941             ty: discr.ty
 942         })?;
 943         let discr_val = match layout.variants {
 944             layout::Variants::Single { .. } => bug!(),
 945             // FIXME: should we catch invalid discriminants here?
 946             layout::Variants::Tagged { .. } => {
 947                 if discr.ty.is_signed() {
 948                     let i = raw_discr.to_bits(discr.size)? as i128;
 949                     // going from layout tag type to typeck discriminant type
 950                     // requires first sign extending with the layout discriminant
 951                     let shift = 128 - discr.size.bits();
 952                     let sexted = (i << shift) >> shift;
 953                     // and then zeroing with the typeck discriminant type
 954                     let discr_ty = layout
 955                         .ty
 956                         .ty_adt_def().expect("tagged layout corresponds to adt")
 957                         .repr
 958                         .discr_type();
 959                     let discr_ty = layout::Integer::from_attr(self.tcx.tcx, discr_ty);
 960                     let shift = 128 - discr_ty.size().bits();
 961                     let truncatee = sexted as u128;
 962                     (truncatee << shift) >> shift
 963                 } else {
 964                     raw_discr.to_bits(discr.size)?
 965                 }
 966             },
 967             layout::Variants::NicheFilling {
 968                 dataful_variant,
 969                 ref niche_variants,
 970                 niche_start,
 971                 ..
 972             } => {
 973                 let variants_start = *niche_variants.start() as u128;
 974                 let variants_end = *niche_variants.end() as u128;
 975                 match raw_discr {
 976                     Scalar::Ptr(_) => {
 977                         assert!(niche_start == 0);
 978                         assert!(variants_start == variants_end);
 979                         dataful_variant as u128
 980                     },
 981                     Scalar::Bits { bits: raw_discr, size } => {
 982                         assert_eq!(size as u64, discr.size.bytes());
 983                         let discr = raw_discr.wrapping_sub(niche_start)
 984                             .wrapping_add(variants_start);
 985                         if variants_start <= discr && discr <= variants_end {
 986                             discr
 987                         } else {
 988                             dataful_variant as u128
 989                         }
 990                     },
 991                 }
 992             }
 993         };
 994
 995         Ok(discr_val)
 996     }
 997
 998
 999     pub fn write_discriminant_value(
1000         &mut self,
1001         dest_ty: Ty<'tcx>,
1002         dest: Place,
1003         variant_index: usize,
1004     ) -> EvalResult<'tcx> {
1005         let layout = self.layout_of(dest_ty)?;
1006
1007         match layout.variants {
1008             layout::Variants::Single { index } => {
1009                 if index != variant_index {
1010                     // If the layout of an enum is `Single`, all
1011                     // other variants are necessarily uninhabited.
1012                     assert_eq!(layout.for_variant(&self, variant_index).abi,
1013                                layout::Abi::Uninhabited);
1014                 }
1015             }
1016             layout::Variants::Tagged { ref tag, .. } => {
1017                 let discr_val = dest_ty.ty_adt_def().unwrap()
1018                     .discriminant_for_variant(*self.tcx, variant_index)
1019                     .val;
1020
1021                 // raw discriminants for enums are isize or bigger during
1022                 // their computation, but the in-memory tag is the smallest possible
1023                 // representation
1024                 let size = tag.value.size(self.tcx.tcx);
1025                 let shift = 128 - size.bits();
1026                 let discr_val = (discr_val << shift) >> shift;
1027
1028                 let (discr_dest, tag) = self.place_field(dest, mir::Field::new(0), layout)?;
1029                 self.write_scalar(discr_dest, Scalar::Bits {
1030                     bits: discr_val,
1031                     size: size.bytes() as u8,
1032                 }, tag.ty)?;
1033             }
1034             layout::Variants::NicheFilling {
1035                 dataful_variant,
1036                 ref niche_variants,
1037                 niche_start,
1038                 ..
1039             } => {
1040                 if variant_index != dataful_variant {
1041                     let (niche_dest, niche) =
1042                         self.place_field(dest, mir::Field::new(0), layout)?;
1043                     let niche_value = ((variant_index - niche_variants.start()) as u128)
1044                         .wrapping_add(niche_start);
1045                     self.write_scalar(niche_dest, Scalar::Bits {
1046                         bits: niche_value,
1047                         size: niche.size.bytes() as u8,
1048                     }, niche.ty)?;
1049                 }
1050             }
1051         }
1052
1053         Ok(())
1054     }
1055
1056     pub fn read_global_as_value(&mut self, gid: GlobalId<'tcx>) -> EvalResult<'tcx, Value> {
1057         let cv = self.const_eval(gid)?;
1058         self.const_to_value(cv.val)
1059     }
1060
1061     pub fn const_eval(&self, gid: GlobalId<'tcx>) -> EvalResult<'tcx, &'tcx ty::Const<'tcx>> {
1062         let param_env = if self.tcx.is_static(gid.instance.def_id()).is_some() {
1063             ty::ParamEnv::reveal_all()
1064         } else {
1065             self.param_env
1066         };
1067         self.tcx.const_eval(param_env.and(gid)).map_err(|err| EvalErrorKind::ReferencedConstant(err).into())
1068     }
1069
1070     pub fn allocate_place_for_value(
1071         &mut self,
1072         value: Value,
1073         layout: TyLayout<'tcx>,
1074         variant: Option<usize>,
1075     ) -> EvalResult<'tcx, Place> {
1076         let (ptr, align) = match value {
1077             Value::ByRef(ptr, align) => (ptr, align),
1078             Value::ScalarPair(..) | Value::Scalar(_) => {
1079                 let ptr = self.alloc_ptr(layout)?.into();
1080                 self.write_value_to_ptr(value, ptr, layout.align, layout.ty)?;
1081                 (ptr, layout.align)
1082             },
1083         };
1084         Ok(Place::Ptr {
1085             ptr,
1086             align,
1087             extra: variant.map_or(PlaceExtra::None, PlaceExtra::DowncastVariant),
1088         })
1089     }
1090
1091     pub fn force_allocation(&mut self, place: Place) -> EvalResult<'tcx, Place> {
1092         let new_place = match place {
1093             Place::Local { frame, local } => {
1094                 match self.stack[frame].locals[local].access()? {
1095                     Value::ByRef(ptr, align) => {
1096                         Place::Ptr {
1097                             ptr: ptr.into(),
1098                             align,
1099                             extra: PlaceExtra::None,
1100                         }
1101                     }
1102                     val => {
1103                         let ty = self.stack[frame].mir.local_decls[local].ty;
1104                         let ty = self.monomorphize(ty, self.stack[frame].instance.substs);
1105                         let layout = self.layout_of(ty)?;
1106                         let ptr = self.alloc_ptr(layout)?;
1107                         self.stack[frame].locals[local] =
1108                             LocalValue::Live(Value::ByRef(ptr.into(), layout.align)); // it stays live
1109
1110                         let place = Place::from_ptr(ptr, layout.align);
1111                         self.write_value(ValTy { value: val, ty }, place)?;
1112                         place
1113                     }
1114                 }
1115             }
1116             Place::Ptr { .. } => place,
1117         };
1118         Ok(new_place)
1119     }
1120
1121     /// ensures this Value is not a ByRef
1122     pub fn follow_by_ref_value(
1123         &mut self,
1124         value: Value,
1125         ty: Ty<'tcx>,
1126     ) -> EvalResult<'tcx, Value> {
1127         match value {
1128             Value::ByRef(ptr, align) => {
1129                 self.read_value(ptr, align, ty)
1130             }
1131             other => Ok(other),
1132         }
1133     }
1134
1135     pub fn value_to_scalar(
1136         &mut self,
1137         ValTy { value, ty } : ValTy<'tcx>,
1138     ) -> EvalResult<'tcx, Scalar> {
1139         match self.follow_by_ref_value(value, ty)? {
1140             Value::ByRef { .. } => bug!("follow_by_ref_value can't result in `ByRef`"),
1141
1142             Value::Scalar(scalar) => Ok(scalar),
1143
1144             Value::ScalarPair(..) => bug!("value_to_scalar can't work with fat pointers"),
1145         }
1146     }
1147
1148     pub fn write_ptr(&mut self, dest: Place, val: Scalar, dest_ty: Ty<'tcx>) -> EvalResult<'tcx> {
1149         let valty = ValTy {
1150             value: val.to_value(),
1151             ty: dest_ty,
1152         };
1153         self.write_value(valty, dest)
1154     }
1155
1156     pub fn write_scalar(
1157         &mut self,
1158         dest: Place,
1159         val: impl Into<ScalarMaybeUndef>,
1160         dest_ty: Ty<'tcx>,
1161     ) -> EvalResult<'tcx> {
1162         let valty = ValTy {
1163             value: Value::Scalar(val.into()),
1164             ty: dest_ty,
1165         };
1166         self.write_value(valty, dest)
1167     }
1168
1169     pub fn write_value(
1170         &mut self,
1171         ValTy { value: src_val, ty: dest_ty } : ValTy<'tcx>,
1172         dest: Place,
1173     ) -> EvalResult<'tcx> {
1174         //trace!("Writing {:?} to {:?} at type {:?}", src_val, dest, dest_ty);
1175         // Note that it is really important that the type here is the right one, and matches the type things are read at.
1176         // In case `src_val` is a `ScalarPair`, we don't do any magic here to handle padding properly, which is only
1177         // correct if we never look at this data with the wrong type.
1178
1179         match dest {
1180             Place::Ptr { ptr, align, extra } => {
1181                 assert_eq!(extra, PlaceExtra::None);
1182                 self.write_value_to_ptr(src_val, ptr.read()?, align, dest_ty)
1183             }
1184
1185             Place::Local { frame, local } => {
1186                 let old_val = self.stack[frame].locals[local].access()?;
1187                 self.write_value_possibly_by_val(
1188                     src_val,
1189                     |this, val| this.stack[frame].set_local(local, val),
1190                     old_val,
1191                     dest_ty,
1192                 )
1193             }
1194         }
1195     }
1196
1197     // The cases here can be a bit subtle. Read carefully!
1198     fn write_value_possibly_by_val<F: FnOnce(&mut Self, Value) -> EvalResult<'tcx>>(
1199         &mut self,
1200         src_val: Value,
1201         write_dest: F,
1202         old_dest_val: Value,
1203         dest_ty: Ty<'tcx>,
1204     ) -> EvalResult<'tcx> {
1205         // FIXME: this should be a layout check, not underlying value
1206         if let Value::ByRef(dest_ptr, align) = old_dest_val {
1207             // If the value is already `ByRef` (that is, backed by an `Allocation`),
1208             // then we must write the new value into this allocation, because there may be
1209             // other pointers into the allocation. These other pointers are logically
1210             // pointers into the local variable, and must be able to observe the change.
1211             //
1212             // Thus, it would be an error to replace the `ByRef` with a `ByVal`, unless we
1213             // knew for certain that there were no outstanding pointers to this allocation.
1214             self.write_value_to_ptr(src_val, dest_ptr, align, dest_ty)?;
1215         } else if let Value::ByRef(src_ptr, align) = src_val {
1216             // If the value is not `ByRef`, then we know there are no pointers to it
1217             // and we can simply overwrite the `Value` in the locals array directly.
1218             //
1219             // In this specific case, where the source value is `ByRef`, we must duplicate
1220             // the allocation, because this is a by-value operation. It would be incorrect
1221             // if they referred to the same allocation, since then a change to one would
1222             // implicitly change the other.
1223             //
1224             // It is a valid optimization to attempt reading a primitive value out of the
1225             // source and write that into the destination without making an allocation, so
1226             // we do so here.
1227             if let Ok(Some(src_val)) = self.try_read_value(src_ptr, align, dest_ty) {
1228                 write_dest(self, src_val)?;
1229             } else {
1230                 let layout = self.layout_of(dest_ty)?;
1231                 let dest_ptr = self.alloc_ptr(layout)?.into();
1232                 self.memory.copy(src_ptr, align.min(layout.align), dest_ptr, layout.align, layout.size, false)?;
1233                 write_dest(self, Value::ByRef(dest_ptr, layout.align))?;
1234             }
1235         } else {
1236             // Finally, we have the simple case where neither source nor destination are
1237             // `ByRef`. We may simply copy the source value over the the destintion.
1238             write_dest(self, src_val)?;
1239         }
1240         Ok(())
1241     }
1242
1243     pub fn write_value_to_ptr(
1244         &mut self,
1245         value: Value,
1246         dest: Scalar,
1247         dest_align: Align,
1248         dest_ty: Ty<'tcx>,
1249     ) -> EvalResult<'tcx> {
1250         let layout = self.layout_of(dest_ty)?;
1251         trace!("write_value_to_ptr: {:#?}, {}, {:#?}", value, dest_ty, layout);
1252         match value {
1253             Value::ByRef(ptr, align) => {
1254                 self.memory.copy(ptr, align.min(layout.align), dest, dest_align.min(layout.align), layout.size, false)
1255             }
1256             Value::Scalar(scalar) => {
1257                 let signed = match layout.abi {
1258                     layout::Abi::Scalar(ref scal) => match scal.value {
1259                         layout::Primitive::Int(_, signed) => signed,
1260                         _ => false,
1261                     },
1262                     _ => false,
1263                 };
1264                 self.memory.write_scalar(dest, dest_align, scalar, layout.size, signed)
1265             }
1266             Value::ScalarPair(a_val, b_val) => {
1267                 trace!("write_value_to_ptr valpair: {:#?}", layout);
1268                 let (a, b) = match layout.abi {
1269                     layout::Abi::ScalarPair(ref a, ref b) => (&a.value, &b.value),
1270                     _ => bug!("write_value_to_ptr: invalid ScalarPair layout: {:#?}", layout)
1271                 };
1272                 let (a_size, b_size) = (a.size(&self), b.size(&self));
1273                 let a_ptr = dest;
1274                 let b_offset = a_size.abi_align(b.align(&self));
1275                 let b_ptr = dest.ptr_offset(b_offset, &self)?.into();
1276                 // TODO: What about signedess?
1277                 self.memory.write_scalar(a_ptr, dest_align, a_val, a_size, false)?;
1278                 self.memory.write_scalar(b_ptr, dest_align, b_val, b_size, false)
1279             }
1280         }
1281     }
1282
1283     pub fn read_value(&self, ptr: Scalar, align: Align, ty: Ty<'tcx>) -> EvalResult<'tcx, Value> {
1284         if let Some(val) = self.try_read_value(ptr, align, ty)? {
1285             Ok(val)
1286         } else {
1287             bug!("primitive read failed for type: {:?}", ty);
1288         }
1289     }
1290
1291     pub(crate) fn read_ptr(
1292         &self,
1293         ptr: Pointer,
1294         ptr_align: Align,
1295         pointee_ty: Ty<'tcx>,
1296     ) -> EvalResult<'tcx, Value> {
1297         let ptr_size = self.memory.pointer_size();
1298         let p: ScalarMaybeUndef = self.memory.read_ptr_sized(ptr, ptr_align)?;
1299         if self.type_is_sized(pointee_ty) {
1300             Ok(Value::Scalar(p))
1301         } else {
1302             trace!("reading fat pointer extra of type {}", pointee_ty);
1303             let extra = ptr.offset(ptr_size, self)?;
1304             match self.tcx.struct_tail(pointee_ty).sty {
1305                 ty::TyDynamic(..) => Ok(Value::ScalarPair(
1306                     p,
1307                     self.memory.read_ptr_sized(extra, ptr_align)?,
1308                 )),
1309                 ty::TySlice(..) | ty::TyStr => {
1310                     let len = self
1311                         .memory
1312                         .read_ptr_sized(extra, ptr_align)?
1313                         .read()?
1314                         .to_bits(ptr_size)?;
1315                     Ok(p.to_value_with_len(len as u64, self.tcx.tcx))
1316                 },
1317                 _ => bug!("unsized scalar ptr read from {:?}", pointee_ty),
1318             }
1319         }
1320     }
1321
1322     fn validate_scalar(
1323         &self,
1324         value: Scalar,
1325         size: Size,
1326         scalar: &layout::Scalar,
1327         path: &str,
1328         ty: Ty,
1329     ) -> EvalResult<'tcx> {
1330         trace!("validate scalar: {:#?}, {:#?}, {:#?}, {}", value, size, scalar, ty);
1331         let (lo, hi) = scalar.valid_range.clone().into_inner();
1332
1333         let (bits, defined) = match value {
1334             Scalar::Bits { bits, defined } => (bits, defined),
1335             Scalar::Ptr(_) => {
1336                 let ptr_size = self.memory.pointer_size();
1337                 let ptr_max = u128::max_value() >> (128 - ptr_size.bits());
1338                 return if lo > hi {
1339                     if lo - hi == 1 {
1340                         // no gap, all values are ok
1341                         Ok(())
1342                     } else if hi < ptr_max || lo > 1 {
1343                         let max = u128::max_value() >> (128 - size.bits());
1344                         validation_failure!(
1345                             "pointer",
1346                             path,
1347                             format!("something in the range {:?} or {:?}", 0..=lo, hi..=max)
1348                         )
1349                     } else {
1350                         Ok(())
1351                     }
1352                 } else if hi < ptr_max || lo > 1 {
1353                     validation_failure!(
1354                         "pointer",
1355                         path,
1356                         format!("something in the range {:?}", scalar.valid_range)
1357                     )
1358                 } else {
1359                     Ok(())
1360                 };
1361             },
1362         };
1363
1364         // char gets a special treatment, because its number space is not contiguous so `TyLayout`
1365         // has no special checks for chars
1366         match ty.sty {
1367             ty::TyChar => {
1368                 debug_assert_eq!(size.bytes(), 4);
1369                 if ::std::char::from_u32(bits as u32).is_none() {
1370                     return err!(InvalidChar(bits));
1371                 }
1372             }
1373             _ => {},
1374         }
1375
1376         use std::ops::RangeInclusive;
1377         let in_range = |bound: RangeInclusive<u128>| {
1378             defined as u64 >= size.bits() && bound.contains(&bits)
1379         };
1380         if lo > hi {
1381             if in_range(0..=hi) || in_range(lo..=u128::max_value()) {
1382                 Ok(())
1383             } else if defined as u64 >= size.bits() {
1384                 validation_failure!(
1385                     bits,
1386                     path,
1387                     format!("something in the range {:?} or {:?}", ..=hi, lo..)
1388                 )
1389             } else {
1390                 validation_failure!("undefined bytes", path)
1391             }
1392         } else {
1393             if in_range(scalar.valid_range.clone()) {
1394                 Ok(())
1395             } else if defined as u64 >= size.bits() {
1396                 validation_failure!(
1397                     bits,
1398                     path,
1399                     format!("something in the range {:?}", scalar.valid_range)
1400                 )
1401             } else {
1402                 validation_failure!("undefined bytes", path)
1403             }
1404         }
1405     }
1406
1407     /// This function checks the memory where `ptr` points to.
1408     /// It will error if the bits at the destination do not match the ones described by the layout.
1409     pub fn validate_ptr_target(
1410         &self,
1411         ptr: Pointer,
1412         ptr_align: Align,
1413         mut layout: TyLayout<'tcx>,
1414         path: String,
1415         seen: &mut FxHashSet<(Pointer, Ty<'tcx>)>,
1416         todo: &mut Vec<(Pointer, Ty<'tcx>, String)>,
1417     ) -> EvalResult<'tcx> {
1418         self.memory.dump_alloc(ptr.alloc_id);
1419         trace!("validate_ptr_target: {:?}, {:#?}", ptr, layout);
1420
1421         let variant;
1422         match layout.variants {
1423             layout::Variants::NicheFilling { niche: ref tag, .. } |
1424             layout::Variants::Tagged { ref tag, .. } => {
1425                 let size = tag.value.size(self);
1426                 let (tag_value, tag_layout) = self.read_field(
1427                     Value::ByRef(ptr.into(), ptr_align),
1428                     None,
1429                     mir::Field::new(0),
1430                     layout,
1431                 )?;
1432                 let tag_value = self.value_to_scalar(ValTy {
1433                     value: tag_value,
1434                     ty: tag_layout.ty,
1435                 })?;
1436                 let path = format!("{}.TAG", path);
1437                 self.validate_scalar(tag_value, size, tag, &path, tag_layout.ty)?;
1438                 let variant_index = self.read_discriminant_as_variant_index(
1439                     Place::from_ptr(ptr, ptr_align),
1440                     layout,
1441                 )?;
1442                 variant = variant_index;
1443                 layout = layout.for_variant(self, variant_index);
1444                 trace!("variant layout: {:#?}", layout);
1445             },
1446             layout::Variants::Single { index } => variant = index,
1447         }
1448         match layout.fields {
1449             // primitives are unions with zero fields
1450             layout::FieldPlacement::Union(0) => {
1451                 match layout.abi {
1452                     // nothing to do, whatever the pointer points to, it is never going to be read
1453                     layout::Abi::Uninhabited => validation_failure!("a value of an uninhabited type", path),
1454                     // check that the scalar is a valid pointer or that its bit range matches the
1455                     // expectation.
1456                     layout::Abi::Scalar(ref scalar) => {
1457                         let size = scalar.value.size(self);
1458                         let value = self.memory.read_scalar(ptr, ptr_align, size)?;
1459                         self.validate_scalar(value, size, scalar, &path, layout.ty)?;
1460                         if scalar.value == Primitive::Pointer {
1461                             // ignore integer pointers, we can't reason about the final hardware
1462                             if let Scalar::Ptr(ptr) = value {
1463                                 let alloc_kind = self.tcx.alloc_map.lock().get(ptr.alloc_id);
1464                                 if let Some(AllocType::Static(did)) = alloc_kind {
1465                                     // statics from other crates are already checked
1466                                     // extern statics should not be validated as they have no body
1467                                     if !did.is_local() || self.tcx.is_foreign_item(did) {
1468                                         return Ok(());
1469                                     }
1470                                 }
1471                                 if let Some(tam) = layout.ty.builtin_deref(false) {
1472                                     // we have not encountered this pointer+layout combination before
1473                                     if seen.insert((ptr, tam.ty)) {
1474                                         todo.push((ptr, tam.ty, format!("(*{})", path)))
1475                                     }
1476                                 }
1477                             }
1478                         }
1479                         Ok(())
1480                     },
1481                     _ => bug!("bad abi for FieldPlacement::Union(0): {:#?}", layout.abi),
1482                 }
1483             }
1484             layout::FieldPlacement::Union(_) => {
1485                 // We can't check unions, their bits are allowed to be anything.
1486                 // The fields don't need to correspond to any bit pattern of the union's fields.
1487                 // See https://github.com/rust-lang/rust/issues/32836#issuecomment-406875389
1488                 Ok(())
1489             },
1490             layout::FieldPlacement::Array { stride, count } => {
1491                 let elem_layout = layout.field(self, 0)?;
1492                 for i in 0..count {
1493                     let mut path = path.clone();
1494                     self.write_field_name(&mut path, layout.ty, i as usize, variant).unwrap();
1495                     self.validate_ptr_target(ptr.offset(stride * i, self)?, ptr_align, elem_layout, path, seen, todo)?;
1496                 }
1497                 Ok(())
1498             },
1499             layout::FieldPlacement::Arbitrary { ref offsets, .. } => {
1500
1501                 // check length field and vtable field
1502                 match layout.ty.builtin_deref(false).map(|tam| &tam.ty.sty) {
1503                     | Some(ty::TyStr)
1504                     | Some(ty::TySlice(_)) => {
1505                         let (len, len_layout) = self.read_field(
1506                             Value::ByRef(ptr.into(), ptr_align),
1507                             None,
1508                             mir::Field::new(1),
1509                             layout,
1510                         )?;
1511                         let len = self.value_to_scalar(ValTy { value: len, ty: len_layout.ty })?;
1512                         if len.to_bits(len_layout.size).is_err() {
1513                             return validation_failure!("length is not a valid integer", path);
1514                         }
1515                     },
1516                     Some(ty::TyDynamic(..)) => {
1517                         let (vtable, vtable_layout) = self.read_field(
1518                             Value::ByRef(ptr.into(), ptr_align),
1519                             None,
1520                             mir::Field::new(1),
1521                             layout,
1522                         )?;
1523                         let vtable = self.value_to_scalar(ValTy { value: vtable, ty: vtable_layout.ty })?;
1524                         if vtable.to_ptr().is_err() {
1525                             return validation_failure!("vtable address is not a pointer", path);
1526                         }
1527                     }
1528                     _ => {},
1529                 }
1530                 for (i, &offset) in offsets.iter().enumerate() {
1531                     let field_layout = layout.field(self, i)?;
1532                     let mut path = path.clone();
1533                     self.write_field_name(&mut path, layout.ty, i, variant).unwrap();
1534                     self.validate_ptr_target(ptr.offset(offset, self)?, ptr_align, field_layout, path, seen, todo)?;
1535                 }
1536                 Ok(())
1537             }
1538         }
1539     }
1540
1541     pub fn try_read_by_ref(&mut self, mut val: Value, ty: Ty<'tcx>) -> EvalResult<'tcx, Value> {
1542         // Convert to ByVal or ScalarPair if possible
1543         if let Value::ByRef(ptr, align) = val {
1544             if let Some(read_val) = self.try_read_value(ptr, align, ty)? {
1545                 val = read_val;
1546             }
1547         }
1548         Ok(val)
1549     }
1550
1551     pub fn try_read_value(&mut self, ptr: Scalar, ptr_align: Align, ty: Ty<'tcx>) -> EvalResult<'tcx, Option<Value>> {
1552         let mut layout = self.layout_of(ty)?;
1553         self.memory.check_align(ptr, ptr_align)?;
1554
1555         if layout.size.bytes() == 0 {
1556             return Ok(Some(Value::Scalar(ScalarMaybeUndef::Scalar(Scalar::Bits { bits: 0, size: 0 }))));
1557         }
1558
1559         let ptr = ptr.to_ptr()?;
1560
1561         match layout.variants {
1562             layout::Variants::NicheFilling { .. } |
1563             layout::Variants::Tagged { .. } => {
1564                 let variant_index = self.read_discriminant_as_variant_index(
1565                     Place::from_ptr(ptr, ptr_align),
1566                     layout.ty,
1567                 )?;
1568                 layout = layout.for_variant(&self, variant_index);
1569                 trace!("variant layout: {:#?}", layout);
1570             },
1571             layout::Variants::Single { .. } => {},
1572         }
1573
1574         match layout.abi {
1575             layout::Abi::Scalar(..) => {
1576                 let scalar = self.memory.read_scalar(ptr, ptr_align, layout.size)?;
1577                 Ok(Some(Value::Scalar(scalar)))
1578             }
1579             layout::Abi::ScalarPair(ref a, ref b) => {
1580                 let (a, b) = (&a.value, &b.value);
1581                 let (a_size, b_size) = (a.size(&self), b.size(&self));
1582                 let a_ptr = ptr;
1583                 let b_offset = a_size.abi_align(b.align(&self));
1584                 let b_ptr = ptr.offset(b_offset, &self)?.into();
1585                 let a_val = self.memory.read_scalar(a_ptr, ptr_align, a_size)?;
1586                 let b_val = self.memory.read_scalar(b_ptr, ptr_align, b_size)?;
1587                 Ok(Some(Value::ScalarPair(a_val, b_val)))
1588             }
1589             _ => Ok(None),
1590         }
1591     }
1592
1593     pub fn frame(&self) -> &Frame<'mir, 'tcx> {
1594         self.stack.last().expect("no call frames exist")
1595     }
1596
1597     pub fn frame_mut(&mut self) -> &mut Frame<'mir, 'tcx> {
1598         self.stack.last_mut().expect("no call frames exist")
1599     }
1600
1601     pub(super) fn mir(&self) -> &'mir mir::Mir<'tcx> {
1602         self.frame().mir
1603     }
1604
1605     pub fn substs(&self) -> &'tcx Substs<'tcx> {
1606         if let Some(frame) = self.stack.last() {
1607             frame.instance.substs
1608         } else {
1609             Substs::empty()
1610         }
1611     }
1612
1613     fn unsize_into_ptr(
1614         &mut self,
1615         src: Value,
1616         src_ty: Ty<'tcx>,
1617         dest: Place,
1618         dest_ty: Ty<'tcx>,
1619         sty: Ty<'tcx>,
1620         dty: Ty<'tcx>,
1621     ) -> EvalResult<'tcx> {
1622         // A<Struct> -> A<Trait> conversion
1623         let (src_pointee_ty, dest_pointee_ty) = self.tcx.struct_lockstep_tails(sty, dty);
1624
1625         match (&src_pointee_ty.sty, &dest_pointee_ty.sty) {
1626             (&ty::TyArray(_, length), &ty::TySlice(_)) => {
1627                 let ptr = self.into_ptr(src)?;
1628                 // u64 cast is from usize to u64, which is always good
1629                 let valty = ValTy {
1630                     value: ptr.to_value_with_len(length.unwrap_usize(self.tcx.tcx), self.tcx.tcx),
1631                     ty: dest_ty,
1632                 };
1633                 self.write_value(valty, dest)
1634             }
1635             (&ty::TyDynamic(..), &ty::TyDynamic(..)) => {
1636                 // For now, upcasts are limited to changes in marker
1637                 // traits, and hence never actually require an actual
1638                 // change to the vtable.
1639                 let valty = ValTy {
1640                     value: src,
1641                     ty: dest_ty,
1642                 };
1643                 self.write_value(valty, dest)
1644             }
1645             (_, &ty::TyDynamic(ref data, _)) => {
1646                 let trait_ref = data.principal().unwrap().with_self_ty(
1647                     *self.tcx,
1648                     src_pointee_ty,
1649                 );
1650                 let trait_ref = self.tcx.erase_regions(&trait_ref);
1651                 let vtable = self.get_vtable(src_pointee_ty, trait_ref)?;
1652                 let ptr = self.into_ptr(src)?;
1653                 let valty = ValTy {
1654                     value: ptr.to_value_with_vtable(vtable),
1655                     ty: dest_ty,
1656                 };
1657                 self.write_value(valty, dest)
1658             }
1659
1660             _ => bug!("invalid unsizing {:?} -> {:?}", src_ty, dest_ty),
1661         }
1662     }
1663
1664     crate fn unsize_into(
1665         &mut self,
1666         src: Value,
1667         src_layout: TyLayout<'tcx>,
1668         dst: Place,
1669         dst_layout: TyLayout<'tcx>,
1670     ) -> EvalResult<'tcx> {
1671         match (&src_layout.ty.sty, &dst_layout.ty.sty) {
1672             (&ty::TyRef(_, s, _), &ty::TyRef(_, d, _)) |
1673             (&ty::TyRef(_, s, _), &ty::TyRawPtr(TypeAndMut { ty: d, .. })) |
1674             (&ty::TyRawPtr(TypeAndMut { ty: s, .. }),
1675              &ty::TyRawPtr(TypeAndMut { ty: d, .. })) => {
1676                 self.unsize_into_ptr(src, src_layout.ty, dst, dst_layout.ty, s, d)
1677             }
1678             (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) => {
1679                 assert_eq!(def_a, def_b);
1680                 if def_a.is_box() || def_b.is_box() {
1681                     if !def_a.is_box() || !def_b.is_box() {
1682                         bug!("invalid unsizing between {:?} -> {:?}", src_layout, dst_layout);
1683                     }
1684                     return self.unsize_into_ptr(
1685                         src,
1686                         src_layout.ty,
1687                         dst,
1688                         dst_layout.ty,
1689                         src_layout.ty.boxed_ty(),
1690                         dst_layout.ty.boxed_ty(),
1691                     );
1692                 }
1693
1694                 // unsizing of generic struct with pointer fields
1695                 // Example: `Arc<T>` -> `Arc<Trait>`
1696                 // here we need to increase the size of every &T thin ptr field to a fat ptr
1697                 for i in 0..src_layout.fields.count() {
1698                     let (dst_f_place, dst_field) =
1699                         self.place_field(dst, mir::Field::new(i), dst_layout)?;
1700                     if dst_field.is_zst() {
1701                         continue;
1702                     }
1703                     let (src_f_value, src_field) = match src {
1704                         Value::ByRef(ptr, align) => {
1705                             let src_place = Place::from_scalar_ptr(ptr.into(), align);
1706                             let (src_f_place, src_field) =
1707                                 self.place_field(src_place, mir::Field::new(i), src_layout)?;
1708                             (self.read_place(src_f_place)?, src_field)
1709                         }
1710                         Value::Scalar(_) | Value::ScalarPair(..) => {
1711                             let src_field = src_layout.field(&self, i)?;
1712                             assert_eq!(src_layout.fields.offset(i).bytes(), 0);
1713                             assert_eq!(src_field.size, src_layout.size);
1714                             (src, src_field)
1715                         }
1716                     };
1717                     if src_field.ty == dst_field.ty {
1718                         self.write_value(ValTy {
1719                             value: src_f_value,
1720                             ty: src_field.ty,
1721                         }, dst_f_place)?;
1722                     } else {
1723                         self.unsize_into(src_f_value, src_field, dst_f_place, dst_field)?;
1724                     }
1725                 }
1726                 Ok(())
1727             }
1728             _ => {
1729                 bug!(
1730                     "unsize_into: invalid conversion: {:?} -> {:?}",
1731                     src_layout,
1732                     dst_layout
1733                 )
1734             }
1735         }
1736     }
1737
1738     pub fn dump_local(&self, place: Place) {
1739         // Debug output
1740         if !log_enabled!(::log::Level::Trace) {
1741             return;
1742         }
1743         match place {
1744             Place::Local { frame, local } => {
1745                 let mut allocs = Vec::new();
1746                 let mut msg = format!("{:?}", local);
1747                 if frame != self.cur_frame() {
1748                     write!(msg, " ({} frames up)", self.cur_frame() - frame).unwrap();
1749                 }
1750                 write!(msg, ":").unwrap();
1751
1752                 match self.stack[frame].locals[local].access() {
1753                     Err(err) => {
1754                         if let EvalErrorKind::DeadLocal = err.kind {
1755                             write!(msg, " is dead").unwrap();
1756                         } else {
1757                             panic!("Failed to access local: {:?}", err);
1758                         }
1759                     }
1760                     Ok(Value::ByRef(ptr, align)) => {
1761                         match ptr {
1762                             Scalar::Ptr(ptr) => {
1763                                 write!(msg, " by align({}) ref:", align.abi()).unwrap();
1764                                 allocs.push(ptr.alloc_id);
1765                             }
1766                             ptr => write!(msg, " integral by ref: {:?}", ptr).unwrap(),
1767                         }
1768                     }
1769                     Ok(Value::Scalar(val)) => {
1770                         write!(msg, " {:?}", val).unwrap();
1771                         if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val {
1772                             allocs.push(ptr.alloc_id);
1773                         }
1774                     }
1775                     Ok(Value::ScalarPair(val1, val2)) => {
1776                         write!(msg, " ({:?}, {:?})", val1, val2).unwrap();
1777                         if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val1 {
1778                             allocs.push(ptr.alloc_id);
1779                         }
1780                         if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val2 {
1781                             allocs.push(ptr.alloc_id);
1782                         }
1783                     }
1784                 }
1785
1786                 trace!("{}", msg);
1787                 self.memory.dump_allocs(allocs);
1788             }
1789             Place::Ptr { ptr, align, .. } => {
1790                 match ptr {
1791                     ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) => {
1792                         trace!("by align({}) ref:", align.abi());
1793                         self.memory.dump_alloc(ptr.alloc_id);
1794                     }
1795                     ptr => trace!(" integral by ref: {:?}", ptr),
1796                 }
1797             }
1798         }
1799     }
1800
1801     pub fn generate_stacktrace(&self, explicit_span: Option<Span>) -> (Vec<FrameInfo>, Span) {
1802         let mut last_span = None;
1803         let mut frames = Vec::new();
1804         // skip 1 because the last frame is just the environment of the constant
1805         for &Frame { instance, span, mir, block, stmt, .. } in self.stack().iter().skip(1).rev() {
1806             // make sure we don't emit frames that are duplicates of the previous
1807             if explicit_span == Some(span) {
1808                 last_span = Some(span);
1809                 continue;
1810             }
1811             if let Some(last) = last_span {
1812                 if last == span {
1813                     continue;
1814                 }
1815             } else {
1816                 last_span = Some(span);
1817             }
1818             let location = if self.tcx.def_key(instance.def_id()).disambiguated_data.data == DefPathData::ClosureExpr {
1819                 "closure".to_owned()
1820             } else {
1821                 instance.to_string()
1822             };
1823             let block = &mir.basic_blocks()[block];
1824             let source_info = if stmt < block.statements.len() {
1825                 block.statements[stmt].source_info
1826             } else {
1827                 block.terminator().source_info
1828             };
1829             let lint_root = match mir.source_scope_local_data {
1830                 mir::ClearCrossCrate::Set(ref ivs) => Some(ivs[source_info.scope].lint_root),
1831                 mir::ClearCrossCrate::Clear => None,
1832             };
1833             frames.push(FrameInfo { span, location, lint_root });
1834         }
1835         trace!("generate stacktrace: {:#?}, {:?}", frames, explicit_span);
1836         (frames, self.tcx.span)
1837     }
1838
1839     pub fn sign_extend(&self, value: u128, ty: TyLayout<'_>) -> u128 {
1840         super::sign_extend(value, ty)
1841     }
1842
1843     pub fn truncate(&self, value: u128, ty: TyLayout<'_>) -> u128 {
1844         super::truncate(value, ty)
1845     }
1846
1847     fn write_field_name(&self, s: &mut String, ty: Ty<'tcx>, i: usize, variant: usize) -> ::std::fmt::Result {
1848         match ty.sty {
1849             ty::TyBool |
1850             ty::TyChar |
1851             ty::TyInt(_) |
1852             ty::TyUint(_) |
1853             ty::TyFloat(_) |
1854             ty::TyFnPtr(_) |
1855             ty::TyNever |
1856             ty::TyFnDef(..) |
1857             ty::TyGeneratorWitness(..) |
1858             ty::TyForeign(..) |
1859             ty::TyDynamic(..) => {
1860                 bug!("field_name({:?}): not applicable", ty)
1861             }
1862
1863             // Potentially-fat pointers.
1864             ty::TyRef(_, pointee, _) |
1865             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
1866                 assert!(i < 2);
1867
1868                 // Reuse the fat *T type as its own thin pointer data field.
1869                 // This provides information about e.g. DST struct pointees
1870                 // (which may have no non-DST form), and will work as long
1871                 // as the `Abi` or `FieldPlacement` is checked by users.
1872                 if i == 0 {
1873                     return write!(s, ".data_ptr");
1874                 }
1875
1876                 match self.tcx.struct_tail(pointee).sty {
1877                     ty::TySlice(_) |
1878                     ty::TyStr => write!(s, ".len"),
1879                     ty::TyDynamic(..) => write!(s, ".vtable_ptr"),
1880                     _ => bug!("field_name({:?}): not applicable", ty)
1881                 }
1882             }
1883
1884             // Arrays and slices.
1885             ty::TyArray(_, _) |
1886             ty::TySlice(_) |
1887             ty::TyStr => write!(s, "[{}]", i),
1888
1889             // generators and closures.
1890             ty::TyClosure(def_id, _) | ty::TyGenerator(def_id, _, _) => {
1891                 let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1892                 let freevar = self.tcx.with_freevars(node_id, |fv| fv[i]);
1893                 write!(s, ".upvar({})", self.tcx.hir.name(freevar.var_id()))
1894             }
1895
1896             ty::TyTuple(_) => write!(s, ".{}", i),
1897
1898             // enums
1899             ty::TyAdt(def, ..) if def.is_enum() => {
1900                 let variant = &def.variants[variant];
1901                 write!(s, ".{}::{}", variant.name, variant.fields[i].ident)
1902             }
1903
1904             // other ADTs.
1905             ty::TyAdt(def, _) => write!(s, ".{}", def.non_enum_variant().fields[i].ident),
1906
1907             ty::TyProjection(_) | ty::TyAnon(..) | ty::TyParam(_) |
1908             ty::TyInfer(_) | ty::TyError => {
1909                 bug!("write_field_name: unexpected type `{}`", ty)
1910             }
1911         }
1912     }
1913
1914     pub fn storage_live(&mut self, local: mir::Local) -> EvalResult<'tcx, LocalValue> {
1915         trace!("{:?} is now live", local);
1916
1917         let ty = self.frame().mir.local_decls[local].ty;
1918         let init = self.init_value(ty)?;
1919         // StorageLive *always* kills the value that's currently stored
1920         Ok(mem::replace(&mut self.frame_mut().locals[local], LocalValue::Live(init)))
1921     }
1922
1923     fn init_value(&mut self, ty: Ty<'tcx>) -> EvalResult<'tcx, Value> {
1924         let ty = self.monomorphize(ty, self.substs());
1925         let layout = self.layout_of(ty)?;
1926         Ok(match layout.abi {
1927             layout::Abi::Scalar(..) => Value::Scalar(ScalarMaybeUndef::Undef),
1928             layout::Abi::ScalarPair(..) => Value::ScalarPair(
1929                 ScalarMaybeUndef::Undef,
1930                 ScalarMaybeUndef::Undef,
1931             ),
1932             _ => Value::ByRef(self.alloc_ptr(ty)?.into(), layout.align),
1933         })
1934     }
1935 }
1936
1937 impl<'mir, 'tcx> Frame<'mir, 'tcx> {
1938     fn set_local(&mut self, local: mir::Local, value: Value) -> EvalResult<'tcx> {
1939         match self.locals[local] {
1940             LocalValue::Dead => err!(DeadLocal),
1941             LocalValue::Live(ref mut local) => {
1942                 *local = value;
1943                 Ok(())
1944             }
1945         }
1946     }
1947
1948     /// Returns the old value of the local
1949     pub fn storage_dead(&mut self, local: mir::Local) -> LocalValue {
1950         trace!("{:?} is now dead", local);
1951
1952         mem::replace(&mut self.locals[local], LocalValue::Dead)
1953     }
1954 }