src/librustc_mir/interpret/eval_context.rs

   1 use std::collections::HashSet;
   2 use std::fmt::Write;
   3
   4 use rustc::hir::def_id::DefId;
   5 use rustc::hir::map::definitions::DefPathData;
   6 use rustc::middle::const_val::ConstVal;
   7 use rustc::mir;
   8 use rustc::traits::Reveal;
   9 use rustc::ty::layout::{self, Size, Align, HasDataLayout, LayoutOf, TyLayout};
  10 use rustc::ty::subst::{Subst, Substs};
  11 use rustc::ty::{self, Ty, TyCtxt};
  12 use rustc_data_structures::indexed_vec::Idx;
  13 use syntax::codemap::{self, DUMMY_SP};
  14 use syntax::ast::Mutability;
  15 use rustc::mir::interpret::{
  16     GlobalId, Value, Pointer, PrimVal, PrimValKind,
  17     EvalError, EvalResult, EvalErrorKind, MemoryPointer,
  18 };
  19
  20 use super::{Place, PlaceExtra, Memory,
  21             HasMemory, MemoryKind, operator,
  22             Machine};
  23
  24 pub struct EvalContext<'a, 'tcx: 'a, M: Machine<'tcx>> {
  25     /// Stores the `Machine` instance.
  26     pub machine: M,
  27
  28     /// The results of the type checker, from rustc.
  29     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
  30
  31     /// Bounds in scope for polymorphic evaluations.
  32     pub param_env: ty::ParamEnv<'tcx>,
  33
  34     /// The virtual memory system.
  35     pub memory: Memory<'a, 'tcx, M>,
  36
  37     /// The virtual call stack.
  38     pub(crate) stack: Vec<Frame<'tcx>>,
  39
  40     /// The maximum number of stack frames allowed
  41     pub(crate) stack_limit: usize,
  42
  43     /// The maximum number of operations that may be executed.
  44     /// This prevents infinite loops and huge computations from freezing up const eval.
  45     /// Remove once halting problem is solved.
  46     pub(crate) steps_remaining: u64,
  47 }
  48
  49 /// A stack frame.
  50 pub struct Frame<'tcx> {
  51     ////////////////////////////////////////////////////////////////////////////////
  52     // Function and callsite information
  53     ////////////////////////////////////////////////////////////////////////////////
  54     /// The MIR for the function called on this frame.
  55     pub mir: &'tcx mir::Mir<'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: codemap::Span,
  62
  63     ////////////////////////////////////////////////////////////////////////////////
  64     // Return place and locals
  65     ////////////////////////////////////////////////////////////////////////////////
  66     /// The block to return to when returning from the current stack frame
  67     pub return_to_block: StackPopCleanup,
  68
  69     /// The location where the result of the current stack frame should be written to.
  70     pub return_place: Place,
  71
  72     /// The list of locals for this stack frame, stored in order as
  73     /// `[arguments..., variables..., temporaries...]`. The locals are stored as `Option<Value>`s.
  74     /// `None` represents a local that is currently dead, while a live local
  75     /// can either directly contain `PrimVal` or refer to some part of an `Allocation`.
  76     ///
  77     /// Before being initialized, arguments are `Value::ByVal(PrimVal::Undef)` and other locals are `None`.
  78     pub locals: Vec<Option<Value>>,
  79
  80     ////////////////////////////////////////////////////////////////////////////////
  81     // Current position within the function
  82     ////////////////////////////////////////////////////////////////////////////////
  83     /// The block that is currently executed (or will be executed after the above call stacks
  84     /// return).
  85     pub block: mir::BasicBlock,
  86
  87     /// The index of the currently evaluated statement.
  88     pub stmt: usize,
  89 }
  90
  91 #[derive(Clone, Debug, Eq, PartialEq, Hash)]
  92 pub enum StackPopCleanup {
  93     /// The stackframe existed to compute the initial value of a static/constant, make sure it
  94     /// isn't modifyable afterwards in case of constants.
  95     /// In case of `static mut`, mark the memory to ensure it's never marked as immutable through
  96     /// references or deallocated
  97     MarkStatic(Mutability),
  98     /// A regular stackframe added due to a function call will need to get forwarded to the next
  99     /// block
 100     Goto(mir::BasicBlock),
 101     /// The main function and diverging functions have nowhere to return to
 102     None,
 103 }
 104
 105 #[derive(Copy, Clone, Debug)]
 106 pub struct ResourceLimits {
 107     pub memory_size: u64,
 108     pub step_limit: u64,
 109     pub stack_limit: usize,
 110 }
 111
 112 impl Default for ResourceLimits {
 113     fn default() -> Self {
 114         ResourceLimits {
 115             memory_size: 100 * 1024 * 1024, // 100 MB
 116             step_limit: 1_000_000,
 117             stack_limit: 100,
 118         }
 119     }
 120 }
 121
 122 #[derive(Copy, Clone, Debug)]
 123 pub struct TyAndPacked<'tcx> {
 124     pub ty: Ty<'tcx>,
 125     pub packed: bool,
 126 }
 127
 128 #[derive(Copy, Clone, Debug)]
 129 pub struct ValTy<'tcx> {
 130     pub value: Value,
 131     pub ty: Ty<'tcx>,
 132 }
 133
 134 impl<'tcx> ::std::ops::Deref for ValTy<'tcx> {
 135     type Target = Value;
 136     fn deref(&self) -> &Value {
 137         &self.value
 138     }
 139 }
 140
 141 impl<'a, 'tcx, M: Machine<'tcx>> HasDataLayout for &'a EvalContext<'a, 'tcx, M> {
 142     #[inline]
 143     fn data_layout(&self) -> &layout::TargetDataLayout {
 144         &self.tcx.data_layout
 145     }
 146 }
 147
 148 impl<'c, 'b, 'a, 'tcx, M: Machine<'tcx>> HasDataLayout
 149     for &'c &'b mut EvalContext<'a, 'tcx, M> {
 150     #[inline]
 151     fn data_layout(&self) -> &layout::TargetDataLayout {
 152         &self.tcx.data_layout
 153     }
 154 }
 155
 156 impl<'a, 'tcx, M: Machine<'tcx>> layout::HasTyCtxt<'tcx> for &'a EvalContext<'a, 'tcx, M> {
 157     #[inline]
 158     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> {
 159         self.tcx
 160     }
 161 }
 162
 163 impl<'c, 'b, 'a, 'tcx, M: Machine<'tcx>> layout::HasTyCtxt<'tcx>
 164     for &'c &'b mut EvalContext<'a, 'tcx, M> {
 165     #[inline]
 166     fn tcx<'d>(&'d self) -> TyCtxt<'d, 'tcx, 'tcx> {
 167         self.tcx
 168     }
 169 }
 170
 171 impl<'a, 'tcx, M: Machine<'tcx>> LayoutOf<Ty<'tcx>> for &'a EvalContext<'a, 'tcx, M> {
 172     type TyLayout = EvalResult<'tcx, TyLayout<'tcx>>;
 173
 174     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
 175         self.tcx.layout_of(self.param_env.and(ty))
 176             .map_err(|layout| EvalErrorKind::Layout(layout).into())
 177     }
 178 }
 179
 180 impl<'c, 'b, 'a, 'tcx, M: Machine<'tcx>> LayoutOf<Ty<'tcx>>
 181     for &'c &'b mut EvalContext<'a, 'tcx, M> {
 182     type TyLayout = EvalResult<'tcx, TyLayout<'tcx>>;
 183
 184     #[inline]
 185     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
 186         (&**self).layout_of(ty)
 187     }
 188 }
 189
 190 impl<'a, 'tcx, M: Machine<'tcx>> EvalContext<'a, 'tcx, M> {
 191     pub fn new(
 192         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 193         param_env: ty::ParamEnv<'tcx>,
 194         limits: ResourceLimits,
 195         machine: M,
 196         memory_data: M::MemoryData,
 197     ) -> Self {
 198         EvalContext {
 199             machine,
 200             tcx,
 201             param_env,
 202             memory: Memory::new(tcx, limits.memory_size, memory_data),
 203             stack: Vec::new(),
 204             stack_limit: limits.stack_limit,
 205             steps_remaining: limits.step_limit,
 206         }
 207     }
 208
 209     pub fn alloc_ptr(&mut self, ty: Ty<'tcx>) -> EvalResult<'tcx, MemoryPointer> {
 210         let layout = self.layout_of(ty)?;
 211         assert!(!layout.is_unsized(), "cannot alloc memory for unsized type");
 212
 213         let size = layout.size.bytes();
 214         self.memory.allocate(size, layout.align, Some(MemoryKind::Stack))
 215     }
 216
 217     pub fn memory(&self) -> &Memory<'a, 'tcx, M> {
 218         &self.memory
 219     }
 220
 221     pub fn memory_mut(&mut self) -> &mut Memory<'a, 'tcx, M> {
 222         &mut self.memory
 223     }
 224
 225     pub fn stack(&self) -> &[Frame<'tcx>] {
 226         &self.stack
 227     }
 228
 229     #[inline]
 230     pub fn cur_frame(&self) -> usize {
 231         assert!(self.stack.len() > 0);
 232         self.stack.len() - 1
 233     }
 234
 235     pub fn str_to_value(&mut self, s: &str) -> EvalResult<'tcx, Value> {
 236         let ptr = self.memory.allocate_cached(s.as_bytes());
 237         Ok(Value::ByValPair(
 238             PrimVal::Ptr(ptr),
 239             PrimVal::from_u128(s.len() as u128),
 240         ))
 241     }
 242
 243     pub(super) fn const_to_value(&mut self, const_val: &ConstVal<'tcx>, ty: Ty<'tcx>) -> EvalResult<'tcx, Value> {
 244         use rustc::middle::const_val::ConstVal::*;
 245
 246         let primval = match *const_val {
 247             Integral(const_int) => PrimVal::Bytes(const_int.to_u128_unchecked()),
 248
 249             Float(val) => PrimVal::Bytes(val.bits),
 250
 251             Bool(b) => PrimVal::from_bool(b),
 252             Char(c) => PrimVal::from_char(c),
 253
 254             Str(ref s) => return self.str_to_value(s),
 255
 256             ByteStr(ref bs) => {
 257                 let ptr = self.memory.allocate_cached(bs.data);
 258                 PrimVal::Ptr(ptr)
 259             }
 260
 261             Unevaluated(def_id, substs) => {
 262                 let instance = self.resolve(def_id, substs)?;
 263                 return Ok(self.read_global_as_value(GlobalId {
 264                     instance,
 265                     promoted: None,
 266                 }, self.layout_of(ty)?));
 267             }
 268
 269             Aggregate(..) |
 270             Variant(_) => bug!("should not have aggregate or variant constants in MIR"),
 271             // function items are zero sized and thus have no readable value
 272             Function(..) => PrimVal::Undef,
 273         };
 274
 275         Ok(Value::ByVal(primval))
 276     }
 277
 278     pub(super) fn resolve(&self, def_id: DefId, substs: &'tcx Substs<'tcx>) -> EvalResult<'tcx, ty::Instance<'tcx>> {
 279         let substs = self.tcx.trans_apply_param_substs(self.substs(), &substs);
 280         ty::Instance::resolve(
 281             self.tcx,
 282             self.param_env,
 283             def_id,
 284             substs,
 285         ).ok_or(EvalErrorKind::TypeckError.into()) // turn error prop into a panic to expose associated type in const issue
 286     }
 287
 288     pub(super) fn type_is_sized(&self, ty: Ty<'tcx>) -> bool {
 289         ty.is_sized(self.tcx.at(DUMMY_SP), self.param_env)
 290     }
 291
 292     pub fn load_mir(
 293         &self,
 294         instance: ty::InstanceDef<'tcx>,
 295     ) -> EvalResult<'tcx, &'tcx mir::Mir<'tcx>> {
 296         // do not continue if typeck errors occurred (can only occur in local crate)
 297         let did = instance.def_id();
 298         if did.is_local() && self.tcx.has_typeck_tables(did) && self.tcx.typeck_tables_of(did).tainted_by_errors {
 299             return err!(TypeckError);
 300         }
 301         trace!("load mir {:?}", instance);
 302         match instance {
 303             ty::InstanceDef::Item(def_id) => {
 304                 self.tcx.maybe_optimized_mir(def_id).ok_or_else(|| {
 305                     EvalErrorKind::NoMirFor(self.tcx.item_path_str(def_id)).into()
 306                 })
 307             }
 308             _ => Ok(self.tcx.instance_mir(instance)),
 309         }
 310     }
 311
 312     pub fn monomorphize(&self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
 313         // miri doesn't care about lifetimes, and will choke on some crazy ones
 314         // let's simply get rid of them
 315         let without_lifetimes = self.tcx.erase_regions(&ty);
 316         let substituted = without_lifetimes.subst(self.tcx, substs);
 317         let substituted = self.tcx.fully_normalize_monormophic_ty(&substituted);
 318         substituted
 319     }
 320
 321     /// Return the size and aligment of the value at the given type.
 322     /// Note that the value does not matter if the type is sized. For unsized types,
 323     /// the value has to be a fat pointer, and we only care about the "extra" data in it.
 324     pub fn size_and_align_of_dst(
 325         &mut self,
 326         ty: Ty<'tcx>,
 327         value: Value,
 328     ) -> EvalResult<'tcx, (Size, Align)> {
 329         let layout = self.layout_of(ty)?;
 330         if !layout.is_unsized() {
 331             Ok(layout.size_and_align())
 332         } else {
 333             match ty.sty {
 334                 ty::TyAdt(..) | ty::TyTuple(..) => {
 335                     // First get the size of all statically known fields.
 336                     // Don't use type_of::sizing_type_of because that expects t to be sized,
 337                     // and it also rounds up to alignment, which we want to avoid,
 338                     // as the unsized field's alignment could be smaller.
 339                     assert!(!ty.is_simd());
 340                     debug!("DST {} layout: {:?}", ty, layout);
 341
 342                     let sized_size = layout.fields.offset(layout.fields.count() - 1);
 343                     let sized_align = layout.align;
 344                     debug!(
 345                         "DST {} statically sized prefix size: {:?} align: {:?}",
 346                         ty,
 347                         sized_size,
 348                         sized_align
 349                     );
 350
 351                     // Recurse to get the size of the dynamically sized field (must be
 352                     // the last field).
 353                     let field_ty = layout.field(&self, layout.fields.count() - 1)?.ty;
 354                     let (unsized_size, unsized_align) =
 355                         self.size_and_align_of_dst(field_ty, value)?;
 356
 357                     // FIXME (#26403, #27023): We should be adding padding
 358                     // to `sized_size` (to accommodate the `unsized_align`
 359                     // required of the unsized field that follows) before
 360                     // summing it with `sized_size`. (Note that since #26403
 361                     // is unfixed, we do not yet add the necessary padding
 362                     // here. But this is where the add would go.)
 363
 364                     // Return the sum of sizes and max of aligns.
 365                     let size = sized_size + unsized_size;
 366
 367                     // Choose max of two known alignments (combined value must
 368                     // be aligned according to more restrictive of the two).
 369                     let align = sized_align.max(unsized_align);
 370
 371                     // Issue #27023: must add any necessary padding to `size`
 372                     // (to make it a multiple of `align`) before returning it.
 373                     //
 374                     // Namely, the returned size should be, in C notation:
 375                     //
 376                     //   `size + ((size & (align-1)) ? align : 0)`
 377                     //
 378                     // emulated via the semi-standard fast bit trick:
 379                     //
 380                     //   `(size + (align-1)) & -align`
 381
 382                     Ok((size.abi_align(align), align))
 383                 }
 384                 ty::TyDynamic(..) => {
 385                     let (_, vtable) = self.into_ptr_vtable_pair(value)?;
 386                     // the second entry in the vtable is the dynamic size of the object.
 387                     self.read_size_and_align_from_vtable(vtable)
 388                 }
 389
 390                 ty::TySlice(_) | ty::TyStr => {
 391                     let (elem_size, align) = layout.field(&self, 0)?.size_and_align();
 392                     let (_, len) = self.into_slice(value)?;
 393                     Ok((elem_size * len, align))
 394                 }
 395
 396                 _ => bug!("size_of_val::<{:?}>", ty),
 397             }
 398         }
 399     }
 400
 401     pub fn push_stack_frame(
 402         &mut self,
 403         instance: ty::Instance<'tcx>,
 404         span: codemap::Span,
 405         mir: &'tcx mir::Mir<'tcx>,
 406         return_place: Place,
 407         return_to_block: StackPopCleanup,
 408     ) -> EvalResult<'tcx> {
 409         ::log_settings::settings().indentation += 1;
 410
 411         /// Return the set of locals that have a storage annotation anywhere
 412         fn collect_storage_annotations<'tcx>(mir: &'tcx mir::Mir<'tcx>) -> HashSet<mir::Local> {
 413             use rustc::mir::StatementKind::*;
 414
 415             let mut set = HashSet::new();
 416             for block in mir.basic_blocks() {
 417                 for stmt in block.statements.iter() {
 418                     match stmt.kind {
 419                         StorageLive(local) |
 420                         StorageDead(local) => {
 421                             set.insert(local);
 422                         }
 423                         _ => {}
 424                     }
 425                 }
 426             }
 427             set
 428         }
 429
 430         // Subtract 1 because `local_decls` includes the ReturnMemoryPointer, but we don't store a local
 431         // `Value` for that.
 432         let num_locals = mir.local_decls.len() - 1;
 433
 434         let locals = {
 435             let annotated_locals = collect_storage_annotations(mir);
 436             let mut locals = vec![None; num_locals];
 437             for i in 0..num_locals {
 438                 let local = mir::Local::new(i + 1);
 439                 if !annotated_locals.contains(&local) {
 440                     locals[i] = Some(Value::ByVal(PrimVal::Undef));
 441                 }
 442             }
 443             locals
 444         };
 445
 446         self.stack.push(Frame {
 447             mir,
 448             block: mir::START_BLOCK,
 449             return_to_block,
 450             return_place,
 451             locals,
 452             span,
 453             instance,
 454             stmt: 0,
 455         });
 456
 457         self.memory.cur_frame = self.cur_frame();
 458
 459         if self.stack.len() > self.stack_limit {
 460             err!(StackFrameLimitReached)
 461         } else {
 462             Ok(())
 463         }
 464     }
 465
 466     pub(super) fn pop_stack_frame(&mut self) -> EvalResult<'tcx> {
 467         ::log_settings::settings().indentation -= 1;
 468         M::end_region(self, None)?;
 469         let frame = self.stack.pop().expect(
 470             "tried to pop a stack frame, but there were none",
 471         );
 472         if !self.stack.is_empty() {
 473             // TODO: Is this the correct time to start considering these accesses as originating from the returned-to stack frame?
 474             self.memory.cur_frame = self.cur_frame();
 475         }
 476         match frame.return_to_block {
 477             StackPopCleanup::MarkStatic(mutable) => {
 478                 if let Place::Ptr { ptr, .. } = frame.return_place {
 479                     // FIXME: to_ptr()? might be too extreme here, static zsts might reach this under certain conditions
 480                     self.memory.mark_static_initalized(
 481                         ptr.to_ptr()?.alloc_id,
 482                         mutable,
 483                     )?
 484                 } else {
 485                     bug!("StackPopCleanup::MarkStatic on: {:?}", frame.return_place);
 486                 }
 487             }
 488             StackPopCleanup::Goto(target) => self.goto_block(target),
 489             StackPopCleanup::None => {}
 490         }
 491         // deallocate all locals that are backed by an allocation
 492         for local in frame.locals {
 493             self.deallocate_local(local)?;
 494         }
 495
 496         Ok(())
 497     }
 498
 499     pub fn deallocate_local(&mut self, local: Option<Value>) -> EvalResult<'tcx> {
 500         if let Some(Value::ByRef(ptr, _align)) = local {
 501             trace!("deallocating local");
 502             let ptr = ptr.to_ptr()?;
 503             self.memory.dump_alloc(ptr.alloc_id);
 504             self.memory.deallocate_local(ptr)?;
 505         };
 506         Ok(())
 507     }
 508
 509     /// Evaluate an assignment statement.
 510     ///
 511     /// There is no separate `eval_rvalue` function. Instead, the code for handling each rvalue
 512     /// type writes its results directly into the memory specified by the place.
 513     pub(super) fn eval_rvalue_into_place(
 514         &mut self,
 515         rvalue: &mir::Rvalue<'tcx>,
 516         place: &mir::Place<'tcx>,
 517     ) -> EvalResult<'tcx> {
 518         let dest = self.eval_place(place)?;
 519         let dest_ty = self.place_ty(place);
 520
 521         use rustc::mir::Rvalue::*;
 522         match *rvalue {
 523             Use(ref operand) => {
 524                 let value = self.eval_operand(operand)?.value;
 525                 let valty = ValTy {
 526                     value,
 527                     ty: dest_ty,
 528                 };
 529                 self.write_value(valty, dest)?;
 530             }
 531
 532             BinaryOp(bin_op, ref left, ref right) => {
 533                 let left = self.eval_operand(left)?;
 534                 let right = self.eval_operand(right)?;
 535                 if self.intrinsic_overflowing(
 536                     bin_op,
 537                     left,
 538                     right,
 539                     dest,
 540                     dest_ty,
 541                 )?
 542                 {
 543                     // There was an overflow in an unchecked binop.  Right now, we consider this an error and bail out.
 544                     // The rationale is that the reason rustc emits unchecked binops in release mode (vs. the checked binops
 545                     // it emits in debug mode) is performance, but it doesn't cost us any performance in miri.
 546                     // If, however, the compiler ever starts transforming unchecked intrinsics into unchecked binops,
 547                     // we have to go back to just ignoring the overflow here.
 548                     return err!(OverflowingMath);
 549                 }
 550             }
 551
 552             CheckedBinaryOp(bin_op, ref left, ref right) => {
 553                 let left = self.eval_operand(left)?;
 554                 let right = self.eval_operand(right)?;
 555                 self.intrinsic_with_overflow(
 556                     bin_op,
 557                     left,
 558                     right,
 559                     dest,
 560                     dest_ty,
 561                 )?;
 562             }
 563
 564             UnaryOp(un_op, ref operand) => {
 565                 let val = self.eval_operand_to_primval(operand)?;
 566                 let kind = self.ty_to_primval_kind(dest_ty)?;
 567                 self.write_primval(
 568                     dest,
 569                     operator::unary_op(un_op, val, kind)?,
 570                     dest_ty,
 571                 )?;
 572             }
 573
 574             Aggregate(ref kind, ref operands) => {
 575                 self.inc_step_counter_and_check_limit(operands.len() as u64)?;
 576
 577                 let (dest, active_field_index) = match **kind {
 578                     mir::AggregateKind::Adt(adt_def, variant_index, _, active_field_index) => {
 579                         self.write_discriminant_value(dest_ty, dest, variant_index)?;
 580                         if adt_def.is_enum() {
 581                             (self.place_downcast(dest, variant_index)?, active_field_index)
 582                         } else {
 583                             (dest, active_field_index)
 584                         }
 585                     }
 586                     _ => (dest, None)
 587                 };
 588
 589                 let layout = self.layout_of(dest_ty)?;
 590                 for (i, operand) in operands.iter().enumerate() {
 591                     let value = self.eval_operand(operand)?;
 592                     // Ignore zero-sized fields.
 593                     if !self.layout_of(value.ty)?.is_zst() {
 594                         let field_index = active_field_index.unwrap_or(i);
 595                         let (field_dest, _) = self.place_field(dest, mir::Field::new(field_index), layout)?;
 596                         self.write_value(value, field_dest)?;
 597                     }
 598                 }
 599             }
 600
 601             Repeat(ref operand, _) => {
 602                 let (elem_ty, length) = match dest_ty.sty {
 603                     ty::TyArray(elem_ty, n) => (elem_ty, n.val.to_const_int().unwrap().to_u64().unwrap()),
 604                     _ => {
 605                         bug!(
 606                             "tried to assign array-repeat to non-array type {:?}",
 607                             dest_ty
 608                         )
 609                     }
 610                 };
 611                 let elem_size = self.layout_of(elem_ty)?.size.bytes();
 612                 let value = self.eval_operand(operand)?.value;
 613
 614                 let (dest, dest_align) = self.force_allocation(dest)?.to_ptr_align();
 615
 616                 // FIXME: speed up repeat filling
 617                 for i in 0..length {
 618                     let elem_dest = dest.offset(i * elem_size, &self)?;
 619                     self.write_value_to_ptr(value, elem_dest, dest_align, elem_ty)?;
 620                 }
 621             }
 622
 623             Len(ref place) => {
 624                 // FIXME(CTFE): don't allow computing the length of arrays in const eval
 625                 let src = self.eval_place(place)?;
 626                 let ty = self.place_ty(place);
 627                 let (_, len) = src.elem_ty_and_len(ty);
 628                 self.write_primval(
 629                     dest,
 630                     PrimVal::from_u128(len as u128),
 631                     dest_ty,
 632                 )?;
 633             }
 634
 635             Ref(_, _, ref place) => {
 636                 let src = self.eval_place(place)?;
 637                 // We ignore the alignment of the place here -- special handling for packed structs ends
 638                 // at the `&` operator.
 639                 let (ptr, _align, extra) = self.force_allocation(src)?.to_ptr_align_extra();
 640
 641                 let val = match extra {
 642                     PlaceExtra::None => ptr.to_value(),
 643                     PlaceExtra::Length(len) => ptr.to_value_with_len(len),
 644                     PlaceExtra::Vtable(vtable) => ptr.to_value_with_vtable(vtable),
 645                     PlaceExtra::DowncastVariant(..) => {
 646                         bug!("attempted to take a reference to an enum downcast place")
 647                     }
 648                 };
 649                 let valty = ValTy {
 650                     value: val,
 651                     ty: dest_ty,
 652                 };
 653                 self.write_value(valty, dest)?;
 654             }
 655
 656             NullaryOp(mir::NullOp::Box, ty) => {
 657                 let ty = self.monomorphize(ty, self.substs());
 658                 M::box_alloc(self, ty, dest)?;
 659             }
 660
 661             NullaryOp(mir::NullOp::SizeOf, ty) => {
 662                 let ty = self.monomorphize(ty, self.substs());
 663                 let layout = self.layout_of(ty)?;
 664                 assert!(!layout.is_unsized(),
 665                         "SizeOf nullary MIR operator called for unsized type");
 666                 self.write_primval(
 667                     dest,
 668                     PrimVal::from_u128(layout.size.bytes() as u128),
 669                     dest_ty,
 670                 )?;
 671             }
 672
 673             Cast(kind, ref operand, cast_ty) => {
 674                 debug_assert_eq!(self.monomorphize(cast_ty, self.substs()), dest_ty);
 675                 use rustc::mir::CastKind::*;
 676                 match kind {
 677                     Unsize => {
 678                         let src = self.eval_operand(operand)?;
 679                         let src_layout = self.layout_of(src.ty)?;
 680                         let dst_layout = self.layout_of(dest_ty)?;
 681                         self.unsize_into(src.value, src_layout, dest, dst_layout)?;
 682                     }
 683
 684                     Misc => {
 685                         let src = self.eval_operand(operand)?;
 686                         if self.type_is_fat_ptr(src.ty) {
 687                             match (src.value, self.type_is_fat_ptr(dest_ty)) {
 688                                 (Value::ByRef { .. }, _) |
 689                                 (Value::ByValPair(..), true) => {
 690                                     let valty = ValTy {
 691                                         value: src.value,
 692                                         ty: dest_ty,
 693                                     };
 694                                     self.write_value(valty, dest)?;
 695                                 }
 696                                 (Value::ByValPair(data, _), false) => {
 697                                     let valty = ValTy {
 698                                         value: Value::ByVal(data),
 699                                         ty: dest_ty,
 700                                     };
 701                                     self.write_value(valty, dest)?;
 702                                 }
 703                                 (Value::ByVal(_), _) => bug!("expected fat ptr"),
 704                             }
 705                         } else {
 706                             let src_val = self.value_to_primval(src)?;
 707                             let dest_val = self.cast_primval(src_val, src.ty, dest_ty)?;
 708                             let valty = ValTy {
 709                                 value: Value::ByVal(dest_val),
 710                                 ty: dest_ty,
 711                             };
 712                             self.write_value(valty, dest)?;
 713                         }
 714                     }
 715
 716                     ReifyFnPointer => {
 717                         match self.eval_operand(operand)?.ty.sty {
 718                             ty::TyFnDef(def_id, substs) => {
 719                                 if self.tcx.has_attr(def_id, "rustc_args_required_const") {
 720                                     bug!("reifying a fn ptr that requires \
 721                                           const arguments");
 722                                 }
 723                                 let instance = self.resolve(def_id, substs)?;
 724                                 let fn_ptr = self.memory.create_fn_alloc(instance);
 725                                 let valty = ValTy {
 726                                     value: Value::ByVal(PrimVal::Ptr(fn_ptr)),
 727                                     ty: dest_ty,
 728                                 };
 729                                 self.write_value(valty, dest)?;
 730                             }
 731                             ref other => bug!("reify fn pointer on {:?}", other),
 732                         }
 733                     }
 734
 735                     UnsafeFnPointer => {
 736                         match dest_ty.sty {
 737                             ty::TyFnPtr(_) => {
 738                                 let mut src = self.eval_operand(operand)?;
 739                                 src.ty = dest_ty;
 740                                 self.write_value(src, dest)?;
 741                             }
 742                             ref other => bug!("fn to unsafe fn cast on {:?}", other),
 743                         }
 744                     }
 745
 746                     ClosureFnPointer => {
 747                         match self.eval_operand(operand)?.ty.sty {
 748                             ty::TyClosure(def_id, substs) => {
 749                                 let substs = self.tcx.trans_apply_param_substs(self.substs(), &substs);
 750                                 let instance = ty::Instance::resolve_closure(
 751                                     self.tcx,
 752                                     def_id,
 753                                     substs,
 754                                     ty::ClosureKind::FnOnce,
 755                                 );
 756                                 let fn_ptr = self.memory.create_fn_alloc(instance);
 757                                 let valty = ValTy {
 758                                     value: Value::ByVal(PrimVal::Ptr(fn_ptr)),
 759                                     ty: dest_ty,
 760                                 };
 761                                 self.write_value(valty, dest)?;
 762                             }
 763                             ref other => bug!("closure fn pointer on {:?}", other),
 764                         }
 765                     }
 766                 }
 767             }
 768
 769             Discriminant(ref place) => {
 770                 let ty = self.place_ty(place);
 771                 let place = self.eval_place(place)?;
 772                 let discr_val = self.read_discriminant_value(place, ty)?;
 773                 if let ty::TyAdt(adt_def, _) = ty.sty {
 774                     trace!("Read discriminant {}, valid discriminants {:?}", discr_val, adt_def.discriminants(self.tcx).collect::<Vec<_>>());
 775                     if adt_def.discriminants(self.tcx).all(|v| {
 776                         discr_val != v.to_u128_unchecked()
 777                     })
 778                     {
 779                         return err!(InvalidDiscriminant);
 780                     }
 781                     self.write_primval(dest, PrimVal::Bytes(discr_val), dest_ty)?;
 782                 } else {
 783                     bug!("rustc only generates Rvalue::Discriminant for enums");
 784                 }
 785             }
 786         }
 787
 788         if log_enabled!(::log::Level::Trace) {
 789             self.dump_local(dest);
 790         }
 791
 792         Ok(())
 793     }
 794
 795     pub(super) fn type_is_fat_ptr(&self, ty: Ty<'tcx>) -> bool {
 796         match ty.sty {
 797             ty::TyRawPtr(ref tam) |
 798             ty::TyRef(_, ref tam) => !self.type_is_sized(tam.ty),
 799             ty::TyAdt(def, _) if def.is_box() => !self.type_is_sized(ty.boxed_ty()),
 800             _ => false,
 801         }
 802     }
 803
 804     pub(super) fn eval_operand_to_primval(
 805         &mut self,
 806         op: &mir::Operand<'tcx>,
 807     ) -> EvalResult<'tcx, PrimVal> {
 808         let valty = self.eval_operand(op)?;
 809         self.value_to_primval(valty)
 810     }
 811
 812     pub(crate) fn operands_to_args(
 813         &mut self,
 814         ops: &[mir::Operand<'tcx>],
 815     ) -> EvalResult<'tcx, Vec<ValTy<'tcx>>> {
 816         ops.into_iter()
 817             .map(|op| self.eval_operand(op))
 818             .collect()
 819     }
 820
 821     pub fn eval_operand(&mut self, op: &mir::Operand<'tcx>) -> EvalResult<'tcx, ValTy<'tcx>> {
 822         use rustc::mir::Operand::*;
 823         let ty = self.monomorphize(op.ty(self.mir(), self.tcx), self.substs());
 824         match *op {
 825             // FIXME: do some more logic on `move` to invalidate the old location
 826             Copy(ref place) |
 827             Move(ref place) => {
 828                 Ok(ValTy {
 829                     value: self.eval_and_read_place(place)?,
 830                     ty
 831                 })
 832             },
 833
 834             Constant(ref constant) => {
 835                 use rustc::mir::Literal;
 836                 let mir::Constant { ref literal, .. } = **constant;
 837                 let value = match *literal {
 838                     Literal::Value { ref value } => self.const_to_value(&value.val, ty)?,
 839
 840                     Literal::Promoted { index } => {
 841                         self.read_global_as_value(GlobalId {
 842                             instance: self.frame().instance,
 843                             promoted: Some(index),
 844                         }, self.layout_of(ty)?)
 845                     }
 846                 };
 847
 848                 Ok(ValTy {
 849                     value,
 850                     ty,
 851                 })
 852             }
 853         }
 854     }
 855
 856     pub fn read_discriminant_value(
 857         &mut self,
 858         place: Place,
 859         ty: Ty<'tcx>,
 860     ) -> EvalResult<'tcx, u128> {
 861         let layout = self.layout_of(ty)?;
 862         //trace!("read_discriminant_value {:#?}", layout);
 863
 864         match layout.variants {
 865             layout::Variants::Single { index } => {
 866                 return Ok(index as u128);
 867             }
 868             layout::Variants::Tagged { .. } |
 869             layout::Variants::NicheFilling { .. } => {},
 870         }
 871
 872         let (discr_place, discr) = self.place_field(place, mir::Field::new(0), layout)?;
 873         let raw_discr = self.value_to_primval(ValTy {
 874             value: self.read_place(discr_place)?,
 875             ty: discr.ty
 876         })?;
 877         let discr_val = match layout.variants {
 878             layout::Variants::Single { .. } => bug!(),
 879             layout::Variants::Tagged { .. } => raw_discr.to_bytes()?,
 880             layout::Variants::NicheFilling {
 881                 dataful_variant,
 882                 ref niche_variants,
 883                 niche_start,
 884                 ..
 885             } => {
 886                 let variants_start = niche_variants.start as u128;
 887                 let variants_end = niche_variants.end as u128;
 888                 match raw_discr {
 889                     PrimVal::Ptr(_) => {
 890                         assert!(niche_start == 0);
 891                         assert!(variants_start == variants_end);
 892                         dataful_variant as u128
 893                     },
 894                     PrimVal::Bytes(raw_discr) => {
 895                         let discr = raw_discr.wrapping_sub(niche_start)
 896                             .wrapping_add(variants_start);
 897                         if variants_start <= discr && discr <= variants_end {
 898                             discr
 899                         } else {
 900                             dataful_variant as u128
 901                         }
 902                     },
 903                     PrimVal::Undef => return err!(ReadUndefBytes),
 904                 }
 905             }
 906         };
 907
 908         Ok(discr_val)
 909     }
 910
 911
 912     pub(crate) fn write_discriminant_value(
 913         &mut self,
 914         dest_ty: Ty<'tcx>,
 915         dest: Place,
 916         variant_index: usize,
 917     ) -> EvalResult<'tcx> {
 918         let layout = self.layout_of(dest_ty)?;
 919
 920         match layout.variants {
 921             layout::Variants::Single { index } => {
 922                 if index != variant_index {
 923                     // If the layout of an enum is `Single`, all
 924                     // other variants are necessarily uninhabited.
 925                     assert_eq!(layout.for_variant(&self, variant_index).abi,
 926                                layout::Abi::Uninhabited);
 927                 }
 928             }
 929             layout::Variants::Tagged { .. } => {
 930                 let discr_val = dest_ty.ty_adt_def().unwrap()
 931                     .discriminant_for_variant(self.tcx, variant_index)
 932                     .to_u128_unchecked();
 933
 934                 let (discr_dest, discr) = self.place_field(dest, mir::Field::new(0), layout)?;
 935                 self.write_primval(discr_dest, PrimVal::Bytes(discr_val), discr.ty)?;
 936             }
 937             layout::Variants::NicheFilling {
 938                 dataful_variant,
 939                 ref niche_variants,
 940                 niche_start,
 941                 ..
 942             } => {
 943                 if variant_index != dataful_variant {
 944                     let (niche_dest, niche) =
 945                         self.place_field(dest, mir::Field::new(0), layout)?;
 946                     let niche_value = ((variant_index - niche_variants.start) as u128)
 947                         .wrapping_add(niche_start);
 948                     self.write_primval(niche_dest, PrimVal::Bytes(niche_value), niche.ty)?;
 949                 }
 950             }
 951         }
 952
 953         Ok(())
 954     }
 955
 956     pub fn read_global_as_value(&self, gid: GlobalId, layout: TyLayout) -> Value {
 957         let alloc = self.tcx.interpret_interner.borrow().get_cached(gid).expect("global not cached");
 958         Value::ByRef(MemoryPointer::new(alloc, 0).into(), layout.align)
 959     }
 960
 961     pub fn force_allocation(&mut self, place: Place) -> EvalResult<'tcx, Place> {
 962         let new_place = match place {
 963             Place::Local { frame, local } => {
 964                 // -1 since we don't store the return value
 965                 match self.stack[frame].locals[local.index() - 1] {
 966                     None => return err!(DeadLocal),
 967                     Some(Value::ByRef(ptr, align)) => {
 968                         Place::Ptr {
 969                             ptr,
 970                             align,
 971                             extra: PlaceExtra::None,
 972                         }
 973                     }
 974                     Some(val) => {
 975                         let ty = self.stack[frame].mir.local_decls[local].ty;
 976                         let ty = self.monomorphize(ty, self.stack[frame].instance.substs);
 977                         let layout = self.layout_of(ty)?;
 978                         let ptr = self.alloc_ptr(ty)?;
 979                         self.stack[frame].locals[local.index() - 1] =
 980                             Some(Value::ByRef(ptr.into(), layout.align)); // it stays live
 981                         let place = Place::from_ptr(ptr, layout.align);
 982                         self.write_value(ValTy { value: val, ty }, place)?;
 983                         place
 984                     }
 985                 }
 986             }
 987             Place::Ptr { .. } => place,
 988         };
 989         Ok(new_place)
 990     }
 991
 992     /// ensures this Value is not a ByRef
 993     pub fn follow_by_ref_value(
 994         &self,
 995         value: Value,
 996         ty: Ty<'tcx>,
 997     ) -> EvalResult<'tcx, Value> {
 998         match value {
 999             Value::ByRef(ptr, align) => {
1000                 self.read_value(ptr, align, ty)
1001             }
1002             other => Ok(other),
1003         }
1004     }
1005
1006     pub fn value_to_primval(
1007         &self,
1008         ValTy { value, ty } : ValTy<'tcx>,
1009     ) -> EvalResult<'tcx, PrimVal> {
1010         match self.follow_by_ref_value(value, ty)? {
1011             Value::ByRef { .. } => bug!("follow_by_ref_value can't result in `ByRef`"),
1012
1013             Value::ByVal(primval) => {
1014                 // TODO: Do we really want insta-UB here?
1015                 self.ensure_valid_value(primval, ty)?;
1016                 Ok(primval)
1017             }
1018
1019             Value::ByValPair(..) => bug!("value_to_primval can't work with fat pointers"),
1020         }
1021     }
1022
1023     pub fn write_ptr(&mut self, dest: Place, val: Pointer, dest_ty: Ty<'tcx>) -> EvalResult<'tcx> {
1024         let valty = ValTy {
1025             value: val.to_value(),
1026             ty: dest_ty,
1027         };
1028         self.write_value(valty, dest)
1029     }
1030
1031     pub fn write_primval(
1032         &mut self,
1033         dest: Place,
1034         val: PrimVal,
1035         dest_ty: Ty<'tcx>,
1036     ) -> EvalResult<'tcx> {
1037         let valty = ValTy {
1038             value: Value::ByVal(val),
1039             ty: dest_ty,
1040         };
1041         self.write_value(valty, dest)
1042     }
1043
1044     pub fn write_value(
1045         &mut self,
1046         ValTy { value: src_val, ty: dest_ty } : ValTy<'tcx>,
1047         dest: Place,
1048     ) -> EvalResult<'tcx> {
1049         //trace!("Writing {:?} to {:?} at type {:?}", src_val, dest, dest_ty);
1050         // Note that it is really important that the type here is the right one, and matches the type things are read at.
1051         // In case `src_val` is a `ByValPair`, we don't do any magic here to handle padding properly, which is only
1052         // correct if we never look at this data with the wrong type.
1053
1054         match dest {
1055             Place::Ptr { ptr, align, extra } => {
1056                 assert_eq!(extra, PlaceExtra::None);
1057                 self.write_value_to_ptr(src_val, ptr, align, dest_ty)
1058             }
1059
1060             Place::Local { frame, local } => {
1061                 let dest = self.stack[frame].get_local(local)?;
1062                 self.write_value_possibly_by_val(
1063                     src_val,
1064                     |this, val| this.stack[frame].set_local(local, val),
1065                     dest,
1066                     dest_ty,
1067                 )
1068             }
1069         }
1070     }
1071
1072     // The cases here can be a bit subtle. Read carefully!
1073     fn write_value_possibly_by_val<F: FnOnce(&mut Self, Value) -> EvalResult<'tcx>>(
1074         &mut self,
1075         src_val: Value,
1076         write_dest: F,
1077         old_dest_val: Value,
1078         dest_ty: Ty<'tcx>,
1079     ) -> EvalResult<'tcx> {
1080         if let Value::ByRef(dest_ptr, align) = old_dest_val {
1081             // If the value is already `ByRef` (that is, backed by an `Allocation`),
1082             // then we must write the new value into this allocation, because there may be
1083             // other pointers into the allocation. These other pointers are logically
1084             // pointers into the local variable, and must be able to observe the change.
1085             //
1086             // Thus, it would be an error to replace the `ByRef` with a `ByVal`, unless we
1087             // knew for certain that there were no outstanding pointers to this allocation.
1088             self.write_value_to_ptr(src_val, dest_ptr, align, dest_ty)?;
1089         } else if let Value::ByRef(src_ptr, align) = src_val {
1090             // If the value is not `ByRef`, then we know there are no pointers to it
1091             // and we can simply overwrite the `Value` in the locals array directly.
1092             //
1093             // In this specific case, where the source value is `ByRef`, we must duplicate
1094             // the allocation, because this is a by-value operation. It would be incorrect
1095             // if they referred to the same allocation, since then a change to one would
1096             // implicitly change the other.
1097             //
1098             // It is a valid optimization to attempt reading a primitive value out of the
1099             // source and write that into the destination without making an allocation, so
1100             // we do so here.
1101             if let Ok(Some(src_val)) = self.try_read_value(src_ptr, align, dest_ty) {
1102                 write_dest(self, src_val)?;
1103             } else {
1104                 let dest_ptr = self.alloc_ptr(dest_ty)?.into();
1105                 let layout = self.layout_of(dest_ty)?;
1106                 self.memory.copy(src_ptr, align.min(layout.align), dest_ptr, layout.align, layout.size.bytes(), false)?;
1107                 write_dest(self, Value::ByRef(dest_ptr, layout.align))?;
1108             }
1109         } else {
1110             // Finally, we have the simple case where neither source nor destination are
1111             // `ByRef`. We may simply copy the source value over the the destintion.
1112             write_dest(self, src_val)?;
1113         }
1114         Ok(())
1115     }
1116
1117     pub fn write_value_to_ptr(
1118         &mut self,
1119         value: Value,
1120         dest: Pointer,
1121         dest_align: Align,
1122         dest_ty: Ty<'tcx>,
1123     ) -> EvalResult<'tcx> {
1124         trace!("write_value_to_ptr: {:#?}", value);
1125         let layout = self.layout_of(dest_ty)?;
1126         match value {
1127             Value::ByRef(ptr, align) => {
1128                 self.memory.copy(ptr, align.min(layout.align), dest, dest_align.min(layout.align), layout.size.bytes(), false)
1129             }
1130             Value::ByVal(primval) => {
1131                 match layout.abi {
1132                     layout::Abi::Scalar(_) => {}
1133                     _ if primval.is_undef() => {}
1134                     _ => bug!("write_value_to_ptr: invalid ByVal layout: {:#?}", layout)
1135                 }
1136                 // TODO: Do we need signedness?
1137                 self.memory.write_primval(dest.to_ptr()?, dest_align, primval, layout.size.bytes(), false)
1138             }
1139             Value::ByValPair(a_val, b_val) => {
1140                 let ptr = dest.to_ptr()?;
1141                 trace!("write_value_to_ptr valpair: {:#?}", layout);
1142                 let (a, b) = match layout.abi {
1143                     layout::Abi::ScalarPair(ref a, ref b) => (&a.value, &b.value),
1144                     _ => bug!("write_value_to_ptr: invalid ByValPair layout: {:#?}", layout)
1145                 };
1146                 let (a_size, b_size) = (a.size(&self), b.size(&self));
1147                 let a_ptr = ptr;
1148                 let b_offset = a_size.abi_align(b.align(&self));
1149                 let b_ptr = ptr.offset(b_offset.bytes(), &self)?.into();
1150                 // TODO: What about signedess?
1151                 self.memory.write_primval(a_ptr, dest_align, a_val, a_size.bytes(), false)?;
1152                 self.memory.write_primval(b_ptr, dest_align, b_val, b_size.bytes(), false)
1153             }
1154         }
1155     }
1156
1157     pub fn ty_to_primval_kind(&self, ty: Ty<'tcx>) -> EvalResult<'tcx, PrimValKind> {
1158         use syntax::ast::FloatTy;
1159
1160         let kind = match ty.sty {
1161             ty::TyBool => PrimValKind::Bool,
1162             ty::TyChar => PrimValKind::Char,
1163
1164             ty::TyInt(int_ty) => {
1165                 use syntax::ast::IntTy::*;
1166                 let size = match int_ty {
1167                     I8 => 1,
1168                     I16 => 2,
1169                     I32 => 4,
1170                     I64 => 8,
1171                     I128 => 16,
1172                     Isize => self.memory.pointer_size(),
1173                 };
1174                 PrimValKind::from_int_size(size)
1175             }
1176
1177             ty::TyUint(uint_ty) => {
1178                 use syntax::ast::UintTy::*;
1179                 let size = match uint_ty {
1180                     U8 => 1,
1181                     U16 => 2,
1182                     U32 => 4,
1183                     U64 => 8,
1184                     U128 => 16,
1185                     Usize => self.memory.pointer_size(),
1186                 };
1187                 PrimValKind::from_uint_size(size)
1188             }
1189
1190             ty::TyFloat(FloatTy::F32) => PrimValKind::F32,
1191             ty::TyFloat(FloatTy::F64) => PrimValKind::F64,
1192
1193             ty::TyFnPtr(_) => PrimValKind::FnPtr,
1194
1195             ty::TyRef(_, ref tam) |
1196             ty::TyRawPtr(ref tam) if self.type_is_sized(tam.ty) => PrimValKind::Ptr,
1197
1198             ty::TyAdt(def, _) if def.is_box() => PrimValKind::Ptr,
1199
1200             ty::TyAdt(..) => {
1201                 match self.layout_of(ty)?.abi {
1202                     layout::Abi::Scalar(ref scalar) => {
1203                         use rustc::ty::layout::Primitive::*;
1204                         match scalar.value {
1205                             Int(i, false) => PrimValKind::from_uint_size(i.size().bytes()),
1206                             Int(i, true) => PrimValKind::from_int_size(i.size().bytes()),
1207                             F32 => PrimValKind::F32,
1208                             F64 => PrimValKind::F64,
1209                             Pointer => PrimValKind::Ptr,
1210                         }
1211                     }
1212
1213                     _ => return err!(TypeNotPrimitive(ty)),
1214                 }
1215             }
1216
1217             _ => return err!(TypeNotPrimitive(ty)),
1218         };
1219
1220         Ok(kind)
1221     }
1222
1223     fn ensure_valid_value(&self, val: PrimVal, ty: Ty<'tcx>) -> EvalResult<'tcx> {
1224         match ty.sty {
1225             ty::TyBool if val.to_bytes()? > 1 => err!(InvalidBool),
1226
1227             ty::TyChar if ::std::char::from_u32(val.to_bytes()? as u32).is_none() => {
1228                 err!(InvalidChar(val.to_bytes()? as u32 as u128))
1229             }
1230
1231             _ => Ok(()),
1232         }
1233     }
1234
1235     pub fn read_value(&self, ptr: Pointer, align: Align, ty: Ty<'tcx>) -> EvalResult<'tcx, Value> {
1236         if let Some(val) = self.try_read_value(ptr, align, ty)? {
1237             Ok(val)
1238         } else {
1239             bug!("primitive read failed for type: {:?}", ty);
1240         }
1241     }
1242
1243     pub(crate) fn read_ptr(
1244         &self,
1245         ptr: MemoryPointer,
1246         ptr_align: Align,
1247         pointee_ty: Ty<'tcx>,
1248     ) -> EvalResult<'tcx, Value> {
1249         let ptr_size = self.memory.pointer_size();
1250         let p: Pointer = self.memory.read_ptr_sized_unsigned(ptr, ptr_align)?.into();
1251         if self.type_is_sized(pointee_ty) {
1252             Ok(p.to_value())
1253         } else {
1254             trace!("reading fat pointer extra of type {}", pointee_ty);
1255             let extra = ptr.offset(ptr_size, self)?;
1256             match self.tcx.struct_tail(pointee_ty).sty {
1257                 ty::TyDynamic(..) => Ok(p.to_value_with_vtable(
1258                     self.memory.read_ptr_sized_unsigned(extra, ptr_align)?.to_ptr()?,
1259                 )),
1260                 ty::TySlice(..) | ty::TyStr => Ok(
1261                     p.to_value_with_len(self.memory.read_ptr_sized_unsigned(extra, ptr_align)?.to_bytes()? as u64),
1262                 ),
1263                 _ => bug!("unsized primval ptr read from {:?}", pointee_ty),
1264             }
1265         }
1266     }
1267
1268     pub fn try_read_value(&self, ptr: Pointer, ptr_align: Align, ty: Ty<'tcx>) -> EvalResult<'tcx, Option<Value>> {
1269         use syntax::ast::FloatTy;
1270
1271         let ptr = ptr.to_ptr()?;
1272         let val = match ty.sty {
1273             ty::TyBool => {
1274                 let val = self.memory.read_primval(ptr, ptr_align, 1, false)?;
1275                 let val = match val {
1276                     PrimVal::Bytes(0) => false,
1277                     PrimVal::Bytes(1) => true,
1278                     // TODO: This seems a little overeager, should reading at bool type already be insta-UB?
1279                     _ => return err!(InvalidBool),
1280                 };
1281                 PrimVal::from_bool(val)
1282             }
1283             ty::TyChar => {
1284                 let c = self.memory.read_primval(ptr, ptr_align, 4, false)?.to_bytes()? as u32;
1285                 match ::std::char::from_u32(c) {
1286                     Some(ch) => PrimVal::from_char(ch),
1287                     None => return err!(InvalidChar(c as u128)),
1288                 }
1289             }
1290
1291             ty::TyInt(int_ty) => {
1292                 use syntax::ast::IntTy::*;
1293                 let size = match int_ty {
1294                     I8 => 1,
1295                     I16 => 2,
1296                     I32 => 4,
1297                     I64 => 8,
1298                     I128 => 16,
1299                     Isize => self.memory.pointer_size(),
1300                 };
1301                 self.memory.read_primval(ptr, ptr_align, size, true)?
1302             }
1303
1304             ty::TyUint(uint_ty) => {
1305                 use syntax::ast::UintTy::*;
1306                 let size = match uint_ty {
1307                     U8 => 1,
1308                     U16 => 2,
1309                     U32 => 4,
1310                     U64 => 8,
1311                     U128 => 16,
1312                     Usize => self.memory.pointer_size(),
1313                 };
1314                 self.memory.read_primval(ptr, ptr_align, size, false)?
1315             }
1316
1317             ty::TyFloat(FloatTy::F32) => {
1318                 PrimVal::Bytes(self.memory.read_primval(ptr, ptr_align, 4, false)?.to_bytes()?)
1319             }
1320             ty::TyFloat(FloatTy::F64) => {
1321                 PrimVal::Bytes(self.memory.read_primval(ptr, ptr_align, 8, false)?.to_bytes()?)
1322             }
1323
1324             ty::TyFnPtr(_) => self.memory.read_ptr_sized_unsigned(ptr, ptr_align)?,
1325             ty::TyRef(_, ref tam) |
1326             ty::TyRawPtr(ref tam) => return self.read_ptr(ptr, ptr_align, tam.ty).map(Some),
1327
1328             ty::TyAdt(def, _) => {
1329                 if def.is_box() {
1330                     return self.read_ptr(ptr, ptr_align, ty.boxed_ty()).map(Some);
1331                 }
1332
1333                 if let layout::Abi::Scalar(ref scalar) = self.layout_of(ty)?.abi {
1334                     let mut signed = false;
1335                     if let layout::Int(_, s) = scalar.value {
1336                         signed = s;
1337                     }
1338                     let size = scalar.value.size(self).bytes();
1339                     self.memory.read_primval(ptr, ptr_align, size, signed)?
1340                 } else {
1341                     return Ok(None);
1342                 }
1343             }
1344
1345             _ => return Ok(None),
1346         };
1347
1348         Ok(Some(Value::ByVal(val)))
1349     }
1350
1351     pub fn frame(&self) -> &Frame<'tcx> {
1352         self.stack.last().expect("no call frames exist")
1353     }
1354
1355     pub fn frame_mut(&mut self) -> &mut Frame<'tcx> {
1356         self.stack.last_mut().expect("no call frames exist")
1357     }
1358
1359     pub(super) fn mir(&self) -> &'tcx mir::Mir<'tcx> {
1360         self.frame().mir
1361     }
1362
1363     pub fn substs(&self) -> &'tcx Substs<'tcx> {
1364         if let Some(frame) = self.stack.last() {
1365             frame.instance.substs
1366         } else {
1367             Substs::empty()
1368         }
1369     }
1370
1371     fn unsize_into_ptr(
1372         &mut self,
1373         src: Value,
1374         src_ty: Ty<'tcx>,
1375         dest: Place,
1376         dest_ty: Ty<'tcx>,
1377         sty: Ty<'tcx>,
1378         dty: Ty<'tcx>,
1379     ) -> EvalResult<'tcx> {
1380         // A<Struct> -> A<Trait> conversion
1381         let (src_pointee_ty, dest_pointee_ty) = self.tcx.struct_lockstep_tails(sty, dty);
1382
1383         match (&src_pointee_ty.sty, &dest_pointee_ty.sty) {
1384             (&ty::TyArray(_, length), &ty::TySlice(_)) => {
1385                 let ptr = self.into_ptr(src)?;
1386                 // u64 cast is from usize to u64, which is always good
1387                 let valty = ValTy {
1388                     value: ptr.to_value_with_len(length.val.to_const_int().unwrap().to_u64().unwrap() ),
1389                     ty: dest_ty,
1390                 };
1391                 self.write_value(valty, dest)
1392             }
1393             (&ty::TyDynamic(..), &ty::TyDynamic(..)) => {
1394                 // For now, upcasts are limited to changes in marker
1395                 // traits, and hence never actually require an actual
1396                 // change to the vtable.
1397                 let valty = ValTy {
1398                     value: src,
1399                     ty: dest_ty,
1400                 };
1401                 self.write_value(valty, dest)
1402             }
1403             (_, &ty::TyDynamic(ref data, _)) => {
1404                 let trait_ref = data.principal().unwrap().with_self_ty(
1405                     self.tcx,
1406                     src_pointee_ty,
1407                 );
1408                 let trait_ref = self.tcx.erase_regions(&trait_ref);
1409                 let vtable = self.get_vtable(src_pointee_ty, trait_ref)?;
1410                 let ptr = self.into_ptr(src)?;
1411                 let valty = ValTy {
1412                     value: ptr.to_value_with_vtable(vtable),
1413                     ty: dest_ty,
1414                 };
1415                 self.write_value(valty, dest)
1416             }
1417
1418             _ => bug!("invalid unsizing {:?} -> {:?}", src_ty, dest_ty),
1419         }
1420     }
1421
1422     fn unsize_into(
1423         &mut self,
1424         src: Value,
1425         src_layout: TyLayout<'tcx>,
1426         dst: Place,
1427         dst_layout: TyLayout<'tcx>,
1428     ) -> EvalResult<'tcx> {
1429         match (&src_layout.ty.sty, &dst_layout.ty.sty) {
1430             (&ty::TyRef(_, ref s), &ty::TyRef(_, ref d)) |
1431             (&ty::TyRef(_, ref s), &ty::TyRawPtr(ref d)) |
1432             (&ty::TyRawPtr(ref s), &ty::TyRawPtr(ref d)) => {
1433                 self.unsize_into_ptr(src, src_layout.ty, dst, dst_layout.ty, s.ty, d.ty)
1434             }
1435             (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) => {
1436                 assert_eq!(def_a, def_b);
1437                 if def_a.is_box() || def_b.is_box() {
1438                     if !def_a.is_box() || !def_b.is_box() {
1439                         bug!("invalid unsizing between {:?} -> {:?}", src_layout, dst_layout);
1440                     }
1441                     return self.unsize_into_ptr(
1442                         src,
1443                         src_layout.ty,
1444                         dst,
1445                         dst_layout.ty,
1446                         src_layout.ty.boxed_ty(),
1447                         dst_layout.ty.boxed_ty(),
1448                     );
1449                 }
1450
1451                 // unsizing of generic struct with pointer fields
1452                 // Example: `Arc<T>` -> `Arc<Trait>`
1453                 // here we need to increase the size of every &T thin ptr field to a fat ptr
1454                 for i in 0..src_layout.fields.count() {
1455                     let (dst_f_place, dst_field) =
1456                         self.place_field(dst, mir::Field::new(i), dst_layout)?;
1457                     if dst_field.is_zst() {
1458                         continue;
1459                     }
1460                     let (src_f_value, src_field) = match src {
1461                         Value::ByRef(ptr, align) => {
1462                             let src_place = Place::from_primval_ptr(ptr, align);
1463                             let (src_f_place, src_field) =
1464                                 self.place_field(src_place, mir::Field::new(i), src_layout)?;
1465                             (self.read_place(src_f_place)?, src_field)
1466                         }
1467                         Value::ByVal(_) | Value::ByValPair(..) => {
1468                             let src_field = src_layout.field(&self, i)?;
1469                             assert_eq!(src_layout.fields.offset(i).bytes(), 0);
1470                             assert_eq!(src_field.size, src_layout.size);
1471                             (src, src_field)
1472                         }
1473                     };
1474                     if src_field.ty == dst_field.ty {
1475                         self.write_value(ValTy {
1476                             value: src_f_value,
1477                             ty: src_field.ty,
1478                         }, dst_f_place)?;
1479                     } else {
1480                         self.unsize_into(src_f_value, src_field, dst_f_place, dst_field)?;
1481                     }
1482                 }
1483                 Ok(())
1484             }
1485             _ => {
1486                 bug!(
1487                     "unsize_into: invalid conversion: {:?} -> {:?}",
1488                     src_layout,
1489                     dst_layout
1490                 )
1491             }
1492         }
1493     }
1494
1495     pub fn dump_local(&self, place: Place) {
1496         // Debug output
1497         match place {
1498             Place::Local { frame, local } => {
1499                 let mut allocs = Vec::new();
1500                 let mut msg = format!("{:?}", local);
1501                 if frame != self.cur_frame() {
1502                     write!(msg, " ({} frames up)", self.cur_frame() - frame).unwrap();
1503                 }
1504                 write!(msg, ":").unwrap();
1505
1506                 match self.stack[frame].get_local(local) {
1507                     Err(EvalError { kind: EvalErrorKind::DeadLocal, .. }) => {
1508                         write!(msg, " is dead").unwrap();
1509                     }
1510                     Err(err) => {
1511                         panic!("Failed to access local: {:?}", err);
1512                     }
1513                     Ok(Value::ByRef(ptr, align)) => {
1514                         match ptr.into_inner_primval() {
1515                             PrimVal::Ptr(ptr) => {
1516                                 write!(msg, " by align({}) ref:", align.abi()).unwrap();
1517                                 allocs.push(ptr.alloc_id);
1518                             }
1519                             ptr => write!(msg, " integral by ref: {:?}", ptr).unwrap(),
1520                         }
1521                     }
1522                     Ok(Value::ByVal(val)) => {
1523                         write!(msg, " {:?}", val).unwrap();
1524                         if let PrimVal::Ptr(ptr) = val {
1525                             allocs.push(ptr.alloc_id);
1526                         }
1527                     }
1528                     Ok(Value::ByValPair(val1, val2)) => {
1529                         write!(msg, " ({:?}, {:?})", val1, val2).unwrap();
1530                         if let PrimVal::Ptr(ptr) = val1 {
1531                             allocs.push(ptr.alloc_id);
1532                         }
1533                         if let PrimVal::Ptr(ptr) = val2 {
1534                             allocs.push(ptr.alloc_id);
1535                         }
1536                     }
1537                 }
1538
1539                 trace!("{}", msg);
1540                 self.memory.dump_allocs(allocs);
1541             }
1542             Place::Ptr { ptr, align, .. } => {
1543                 match ptr.into_inner_primval() {
1544                     PrimVal::Ptr(ptr) => {
1545                         trace!("by align({}) ref:", align.abi());
1546                         self.memory.dump_alloc(ptr.alloc_id);
1547                     }
1548                     ptr => trace!(" integral by ref: {:?}", ptr),
1549                 }
1550             }
1551         }
1552     }
1553
1554     /// Convenience function to ensure correct usage of locals
1555     pub fn modify_local<F>(&mut self, frame: usize, local: mir::Local, f: F) -> EvalResult<'tcx>
1556     where
1557         F: FnOnce(&mut Self, Value) -> EvalResult<'tcx, Value>,
1558     {
1559         let val = self.stack[frame].get_local(local)?;
1560         let new_val = f(self, val)?;
1561         self.stack[frame].set_local(local, new_val)?;
1562         // FIXME(solson): Run this when setting to Undef? (See previous version of this code.)
1563         // if let Value::ByRef(ptr) = self.stack[frame].get_local(local) {
1564         //     self.memory.deallocate(ptr)?;
1565         // }
1566         Ok(())
1567     }
1568
1569     pub fn report(&self, e: &mut EvalError) {
1570         if let Some(ref mut backtrace) = e.backtrace {
1571             let mut trace_text = "\n\nAn error occurred in miri:\n".to_string();
1572             backtrace.resolve();
1573             write!(trace_text, "backtrace frames: {}\n", backtrace.frames().len()).unwrap();
1574             'frames: for (i, frame) in backtrace.frames().iter().enumerate() {
1575                 if frame.symbols().is_empty() {
1576                     write!(trace_text, "{}: no symbols\n", i).unwrap();
1577                 }
1578                 for symbol in frame.symbols() {
1579                     write!(trace_text, "{}: ", i).unwrap();
1580                     if let Some(name) = symbol.name() {
1581                         write!(trace_text, "{}\n", name).unwrap();
1582                     } else {
1583                         write!(trace_text, "<unknown>\n").unwrap();
1584                     }
1585                     write!(trace_text, "\tat ").unwrap();
1586                     if let Some(file_path) = symbol.filename() {
1587                         write!(trace_text, "{}", file_path.display()).unwrap();
1588                     } else {
1589                         write!(trace_text, "<unknown_file>").unwrap();
1590                     }
1591                     if let Some(line) = symbol.lineno() {
1592                         write!(trace_text, ":{}\n", line).unwrap();
1593                     } else {
1594                         write!(trace_text, "\n").unwrap();
1595                     }
1596                 }
1597             }
1598             error!("{}", trace_text);
1599         }
1600         if let Some(frame) = self.stack().last() {
1601             let block = &frame.mir.basic_blocks()[frame.block];
1602             let span = if frame.stmt < block.statements.len() {
1603                 block.statements[frame.stmt].source_info.span
1604             } else {
1605                 block.terminator().source_info.span
1606             };
1607             let mut err = self.tcx.sess.struct_span_err(span, &e.to_string());
1608             for &Frame { instance, span, .. } in self.stack().iter().rev() {
1609                 if self.tcx.def_key(instance.def_id()).disambiguated_data.data ==
1610                     DefPathData::ClosureExpr
1611                 {
1612                     err.span_note(span, "inside call to closure");
1613                     continue;
1614                 }
1615                 err.span_note(span, &format!("inside call to {}", instance));
1616             }
1617             err.emit();
1618         } else {
1619             self.tcx.sess.err(&e.to_string());
1620         }
1621     }
1622 }
1623
1624 impl<'tcx> Frame<'tcx> {
1625     pub fn get_local(&self, local: mir::Local) -> EvalResult<'tcx, Value> {
1626         // Subtract 1 because we don't store a value for the ReturnPointer, the local with index 0.
1627         self.locals[local.index() - 1].ok_or(EvalErrorKind::DeadLocal.into())
1628     }
1629
1630     fn set_local(&mut self, local: mir::Local, value: Value) -> EvalResult<'tcx> {
1631         // Subtract 1 because we don't store a value for the ReturnPointer, the local with index 0.
1632         match self.locals[local.index() - 1] {
1633             None => err!(DeadLocal),
1634             Some(ref mut local) => {
1635                 *local = value;
1636                 Ok(())
1637             }
1638         }
1639     }
1640
1641     pub fn storage_live(&mut self, local: mir::Local) -> EvalResult<'tcx, Option<Value>> {
1642         trace!("{:?} is now live", local);
1643
1644         let old = self.locals[local.index() - 1];
1645         self.locals[local.index() - 1] = Some(Value::ByVal(PrimVal::Undef)); // StorageLive *always* kills the value that's currently stored
1646         return Ok(old);
1647     }
1648
1649     /// Returns the old value of the local
1650     pub fn storage_dead(&mut self, local: mir::Local) -> EvalResult<'tcx, Option<Value>> {
1651         trace!("{:?} is now dead", local);
1652
1653         let old = self.locals[local.index() - 1];
1654         self.locals[local.index() - 1] = None;
1655         return Ok(old);
1656     }
1657 }
1658
1659 // TODO(solson): Upstream these methods into rustc::ty::layout.
1660
1661 pub fn resolve_drop_in_place<'a, 'tcx>(
1662     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1663     ty: Ty<'tcx>,
1664 ) -> ty::Instance<'tcx> {
1665     let def_id = tcx.require_lang_item(::rustc::middle::lang_items::DropInPlaceFnLangItem);
1666     let substs = tcx.intern_substs(&[ty.into()]);
1667     ty::Instance::resolve(tcx, ty::ParamEnv::empty(Reveal::All), def_id, substs).unwrap()
1668 }