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, Kind};
  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 statment.
  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, self.param_env).layout_of(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, self.param_env, DUMMY_SP)
 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                                 let instance = self.resolve(def_id, substs)?;
 720                                 let fn_ptr = self.memory.create_fn_alloc(instance);
 721                                 let valty = ValTy {
 722                                     value: Value::ByVal(PrimVal::Ptr(fn_ptr)),
 723                                     ty: dest_ty,
 724                                 };
 725                                 self.write_value(valty, dest)?;
 726                             }
 727                             ref other => bug!("reify fn pointer on {:?}", other),
 728                         }
 729                     }
 730
 731                     UnsafeFnPointer => {
 732                         match dest_ty.sty {
 733                             ty::TyFnPtr(_) => {
 734                                 let mut src = self.eval_operand(operand)?;
 735                                 src.ty = dest_ty;
 736                                 self.write_value(src, dest)?;
 737                             }
 738                             ref other => bug!("fn to unsafe fn cast on {:?}", other),
 739                         }
 740                     }
 741
 742                     ClosureFnPointer => {
 743                         match self.eval_operand(operand)?.ty.sty {
 744                             ty::TyClosure(def_id, substs) => {
 745                                 let substs = self.tcx.trans_apply_param_substs(self.substs(), &substs);
 746                                 let instance = ty::Instance::resolve_closure(
 747                                     self.tcx,
 748                                     def_id,
 749                                     substs,
 750                                     ty::ClosureKind::FnOnce,
 751                                 );
 752                                 let fn_ptr = self.memory.create_fn_alloc(instance);
 753                                 let valty = ValTy {
 754                                     value: Value::ByVal(PrimVal::Ptr(fn_ptr)),
 755                                     ty: dest_ty,
 756                                 };
 757                                 self.write_value(valty, dest)?;
 758                             }
 759                             ref other => bug!("closure fn pointer on {:?}", other),
 760                         }
 761                     }
 762                 }
 763             }
 764
 765             Discriminant(ref place) => {
 766                 let ty = self.place_ty(place);
 767                 let place = self.eval_place(place)?;
 768                 let discr_val = self.read_discriminant_value(place, ty)?;
 769                 if let ty::TyAdt(adt_def, _) = ty.sty {
 770                     trace!("Read discriminant {}, valid discriminants {:?}", discr_val, adt_def.discriminants(self.tcx).collect::<Vec<_>>());
 771                     if adt_def.discriminants(self.tcx).all(|v| {
 772                         discr_val != v.to_u128_unchecked()
 773                     })
 774                     {
 775                         return err!(InvalidDiscriminant);
 776                     }
 777                     self.write_primval(dest, PrimVal::Bytes(discr_val), dest_ty)?;
 778                 } else {
 779                     bug!("rustc only generates Rvalue::Discriminant for enums");
 780                 }
 781             }
 782         }
 783
 784         if log_enabled!(::log::Level::Trace) {
 785             self.dump_local(dest);
 786         }
 787
 788         Ok(())
 789     }
 790
 791     pub(super) fn type_is_fat_ptr(&self, ty: Ty<'tcx>) -> bool {
 792         match ty.sty {
 793             ty::TyRawPtr(ref tam) |
 794             ty::TyRef(_, ref tam) => !self.type_is_sized(tam.ty),
 795             ty::TyAdt(def, _) if def.is_box() => !self.type_is_sized(ty.boxed_ty()),
 796             _ => false,
 797         }
 798     }
 799
 800     pub(super) fn eval_operand_to_primval(
 801         &mut self,
 802         op: &mir::Operand<'tcx>,
 803     ) -> EvalResult<'tcx, PrimVal> {
 804         let valty = self.eval_operand(op)?;
 805         self.value_to_primval(valty)
 806     }
 807
 808     pub(crate) fn operands_to_args(
 809         &mut self,
 810         ops: &[mir::Operand<'tcx>],
 811     ) -> EvalResult<'tcx, Vec<ValTy<'tcx>>> {
 812         ops.into_iter()
 813             .map(|op| self.eval_operand(op))
 814             .collect()
 815     }
 816
 817     pub fn eval_operand(&mut self, op: &mir::Operand<'tcx>) -> EvalResult<'tcx, ValTy<'tcx>> {
 818         use rustc::mir::Operand::*;
 819         let ty = self.monomorphize(op.ty(self.mir(), self.tcx), self.substs());
 820         match *op {
 821             // FIXME: do some more logic on `move` to invalidate the old location
 822             Copy(ref place) |
 823             Move(ref place) => {
 824                 Ok(ValTy {
 825                     value: self.eval_and_read_place(place)?,
 826                     ty
 827                 })
 828             },
 829
 830             Constant(ref constant) => {
 831                 use rustc::mir::Literal;
 832                 let mir::Constant { ref literal, .. } = **constant;
 833                 let value = match *literal {
 834                     Literal::Value { ref value } => self.const_to_value(&value.val, ty)?,
 835
 836                     Literal::Promoted { index } => {
 837                         self.read_global_as_value(GlobalId {
 838                             instance: self.frame().instance,
 839                             promoted: Some(index),
 840                         }, self.layout_of(ty)?)
 841                     }
 842                 };
 843
 844                 Ok(ValTy {
 845                     value,
 846                     ty,
 847                 })
 848             }
 849         }
 850     }
 851
 852     pub fn read_discriminant_value(
 853         &mut self,
 854         place: Place,
 855         ty: Ty<'tcx>,
 856     ) -> EvalResult<'tcx, u128> {
 857         let layout = self.layout_of(ty)?;
 858         //trace!("read_discriminant_value {:#?}", layout);
 859
 860         match layout.variants {
 861             layout::Variants::Single { index } => {
 862                 return Ok(index as u128);
 863             }
 864             layout::Variants::Tagged { .. } |
 865             layout::Variants::NicheFilling { .. } => {},
 866         }
 867
 868         let (discr_place, discr) = self.place_field(place, mir::Field::new(0), layout)?;
 869         let raw_discr = self.value_to_primval(ValTy {
 870             value: self.read_place(discr_place)?,
 871             ty: discr.ty
 872         })?;
 873         let discr_val = match layout.variants {
 874             layout::Variants::Single { .. } => bug!(),
 875             layout::Variants::Tagged { .. } => raw_discr.to_bytes()?,
 876             layout::Variants::NicheFilling {
 877                 dataful_variant,
 878                 ref niche_variants,
 879                 niche_start,
 880                 ..
 881             } => {
 882                 let variants_start = niche_variants.start as u128;
 883                 let variants_end = niche_variants.end as u128;
 884                 match raw_discr {
 885                     PrimVal::Ptr(_) => {
 886                         assert!(niche_start == 0);
 887                         assert!(variants_start == variants_end);
 888                         dataful_variant as u128
 889                     },
 890                     PrimVal::Bytes(raw_discr) => {
 891                         let discr = raw_discr.wrapping_sub(niche_start)
 892                             .wrapping_add(variants_start);
 893                         if variants_start <= discr && discr <= variants_end {
 894                             discr
 895                         } else {
 896                             dataful_variant as u128
 897                         }
 898                     },
 899                     PrimVal::Undef => return err!(ReadUndefBytes),
 900                 }
 901             }
 902         };
 903
 904         Ok(discr_val)
 905     }
 906
 907
 908     pub(crate) fn write_discriminant_value(
 909         &mut self,
 910         dest_ty: Ty<'tcx>,
 911         dest: Place,
 912         variant_index: usize,
 913     ) -> EvalResult<'tcx> {
 914         let layout = self.layout_of(dest_ty)?;
 915
 916         match layout.variants {
 917             layout::Variants::Single { index } => {
 918                 if index != variant_index {
 919                     // If the layout of an enum is `Single`, all
 920                     // other variants are necessarily uninhabited.
 921                     assert_eq!(layout.for_variant(&self, variant_index).abi,
 922                                layout::Abi::Uninhabited);
 923                 }
 924             }
 925             layout::Variants::Tagged { .. } => {
 926                 let discr_val = dest_ty.ty_adt_def().unwrap()
 927                     .discriminant_for_variant(self.tcx, variant_index)
 928                     .to_u128_unchecked();
 929
 930                 let (discr_dest, discr) = self.place_field(dest, mir::Field::new(0), layout)?;
 931                 self.write_primval(discr_dest, PrimVal::Bytes(discr_val), discr.ty)?;
 932             }
 933             layout::Variants::NicheFilling {
 934                 dataful_variant,
 935                 ref niche_variants,
 936                 niche_start,
 937                 ..
 938             } => {
 939                 if variant_index != dataful_variant {
 940                     let (niche_dest, niche) =
 941                         self.place_field(dest, mir::Field::new(0), layout)?;
 942                     let niche_value = ((variant_index - niche_variants.start) as u128)
 943                         .wrapping_add(niche_start);
 944                     self.write_primval(niche_dest, PrimVal::Bytes(niche_value), niche.ty)?;
 945                 }
 946             }
 947         }
 948
 949         Ok(())
 950     }
 951
 952     pub fn read_global_as_value(&self, gid: GlobalId, layout: TyLayout) -> Value {
 953         let alloc = self.tcx.interpret_interner.borrow().get_cached(gid).expect("global not cached");
 954         Value::ByRef(MemoryPointer::new(alloc, 0).into(), layout.align)
 955     }
 956
 957     pub fn force_allocation(&mut self, place: Place) -> EvalResult<'tcx, Place> {
 958         let new_place = match place {
 959             Place::Local { frame, local } => {
 960                 // -1 since we don't store the return value
 961                 match self.stack[frame].locals[local.index() - 1] {
 962                     None => return err!(DeadLocal),
 963                     Some(Value::ByRef(ptr, align)) => {
 964                         Place::Ptr {
 965                             ptr,
 966                             align,
 967                             extra: PlaceExtra::None,
 968                         }
 969                     }
 970                     Some(val) => {
 971                         let ty = self.stack[frame].mir.local_decls[local].ty;
 972                         let ty = self.monomorphize(ty, self.stack[frame].instance.substs);
 973                         let layout = self.layout_of(ty)?;
 974                         let ptr = self.alloc_ptr(ty)?;
 975                         self.stack[frame].locals[local.index() - 1] =
 976                             Some(Value::ByRef(ptr.into(), layout.align)); // it stays live
 977                         let place = Place::from_ptr(ptr, layout.align);
 978                         self.write_value(ValTy { value: val, ty }, place)?;
 979                         place
 980                     }
 981                 }
 982             }
 983             Place::Ptr { .. } => place,
 984         };
 985         Ok(new_place)
 986     }
 987
 988     /// ensures this Value is not a ByRef
 989     pub fn follow_by_ref_value(
 990         &self,
 991         value: Value,
 992         ty: Ty<'tcx>,
 993     ) -> EvalResult<'tcx, Value> {
 994         match value {
 995             Value::ByRef(ptr, align) => {
 996                 self.read_value(ptr, align, ty)
 997             }
 998             other => Ok(other),
 999         }
1000     }
1001
1002     pub fn value_to_primval(
1003         &self,
1004         ValTy { value, ty } : ValTy<'tcx>,
1005     ) -> EvalResult<'tcx, PrimVal> {
1006         match self.follow_by_ref_value(value, ty)? {
1007             Value::ByRef { .. } => bug!("follow_by_ref_value can't result in `ByRef`"),
1008
1009             Value::ByVal(primval) => {
1010                 // TODO: Do we really want insta-UB here?
1011                 self.ensure_valid_value(primval, ty)?;
1012                 Ok(primval)
1013             }
1014
1015             Value::ByValPair(..) => bug!("value_to_primval can't work with fat pointers"),
1016         }
1017     }
1018
1019     pub fn write_ptr(&mut self, dest: Place, val: Pointer, dest_ty: Ty<'tcx>) -> EvalResult<'tcx> {
1020         let valty = ValTy {
1021             value: val.to_value(),
1022             ty: dest_ty,
1023         };
1024         self.write_value(valty, dest)
1025     }
1026
1027     pub fn write_primval(
1028         &mut self,
1029         dest: Place,
1030         val: PrimVal,
1031         dest_ty: Ty<'tcx>,
1032     ) -> EvalResult<'tcx> {
1033         let valty = ValTy {
1034             value: Value::ByVal(val),
1035             ty: dest_ty,
1036         };
1037         self.write_value(valty, dest)
1038     }
1039
1040     pub fn write_value(
1041         &mut self,
1042         ValTy { value: src_val, ty: dest_ty } : ValTy<'tcx>,
1043         dest: Place,
1044     ) -> EvalResult<'tcx> {
1045         //trace!("Writing {:?} to {:?} at type {:?}", src_val, dest, dest_ty);
1046         // Note that it is really important that the type here is the right one, and matches the type things are read at.
1047         // In case `src_val` is a `ByValPair`, we don't do any magic here to handle padding properly, which is only
1048         // correct if we never look at this data with the wrong type.
1049
1050         match dest {
1051             Place::Ptr { ptr, align, extra } => {
1052                 assert_eq!(extra, PlaceExtra::None);
1053                 self.write_value_to_ptr(src_val, ptr, align, dest_ty)
1054             }
1055
1056             Place::Local { frame, local } => {
1057                 let dest = self.stack[frame].get_local(local)?;
1058                 self.write_value_possibly_by_val(
1059                     src_val,
1060                     |this, val| this.stack[frame].set_local(local, val),
1061                     dest,
1062                     dest_ty,
1063                 )
1064             }
1065         }
1066     }
1067
1068     // The cases here can be a bit subtle. Read carefully!
1069     fn write_value_possibly_by_val<F: FnOnce(&mut Self, Value) -> EvalResult<'tcx>>(
1070         &mut self,
1071         src_val: Value,
1072         write_dest: F,
1073         old_dest_val: Value,
1074         dest_ty: Ty<'tcx>,
1075     ) -> EvalResult<'tcx> {
1076         if let Value::ByRef(dest_ptr, align) = old_dest_val {
1077             // If the value is already `ByRef` (that is, backed by an `Allocation`),
1078             // then we must write the new value into this allocation, because there may be
1079             // other pointers into the allocation. These other pointers are logically
1080             // pointers into the local variable, and must be able to observe the change.
1081             //
1082             // Thus, it would be an error to replace the `ByRef` with a `ByVal`, unless we
1083             // knew for certain that there were no outstanding pointers to this allocation.
1084             self.write_value_to_ptr(src_val, dest_ptr, align, dest_ty)?;
1085         } else if let Value::ByRef(src_ptr, align) = src_val {
1086             // If the value is not `ByRef`, then we know there are no pointers to it
1087             // and we can simply overwrite the `Value` in the locals array directly.
1088             //
1089             // In this specific case, where the source value is `ByRef`, we must duplicate
1090             // the allocation, because this is a by-value operation. It would be incorrect
1091             // if they referred to the same allocation, since then a change to one would
1092             // implicitly change the other.
1093             //
1094             // It is a valid optimization to attempt reading a primitive value out of the
1095             // source and write that into the destination without making an allocation, so
1096             // we do so here.
1097             if let Ok(Some(src_val)) = self.try_read_value(src_ptr, align, dest_ty) {
1098                 write_dest(self, src_val)?;
1099             } else {
1100                 let dest_ptr = self.alloc_ptr(dest_ty)?.into();
1101                 let layout = self.layout_of(dest_ty)?;
1102                 self.memory.copy(src_ptr, align.min(layout.align), dest_ptr, layout.align, layout.size.bytes(), false)?;
1103                 write_dest(self, Value::ByRef(dest_ptr, layout.align))?;
1104             }
1105         } else {
1106             // Finally, we have the simple case where neither source nor destination are
1107             // `ByRef`. We may simply copy the source value over the the destintion.
1108             write_dest(self, src_val)?;
1109         }
1110         Ok(())
1111     }
1112
1113     pub fn write_value_to_ptr(
1114         &mut self,
1115         value: Value,
1116         dest: Pointer,
1117         dest_align: Align,
1118         dest_ty: Ty<'tcx>,
1119     ) -> EvalResult<'tcx> {
1120         trace!("write_value_to_ptr: {:#?}", value);
1121         let layout = self.layout_of(dest_ty)?;
1122         match value {
1123             Value::ByRef(ptr, align) => {
1124                 self.memory.copy(ptr, align.min(layout.align), dest, dest_align.min(layout.align), layout.size.bytes(), false)
1125             }
1126             Value::ByVal(primval) => {
1127                 match layout.abi {
1128                     layout::Abi::Scalar(_) => {}
1129                     _ if primval.is_undef() => {}
1130                     _ => bug!("write_value_to_ptr: invalid ByVal layout: {:#?}", layout)
1131                 }
1132                 // TODO: Do we need signedness?
1133                 self.memory.write_primval(dest.to_ptr()?, dest_align, primval, layout.size.bytes(), false)
1134             }
1135             Value::ByValPair(a_val, b_val) => {
1136                 let ptr = dest.to_ptr()?;
1137                 trace!("write_value_to_ptr valpair: {:#?}", layout);
1138                 let (a, b) = match layout.abi {
1139                     layout::Abi::ScalarPair(ref a, ref b) => (&a.value, &b.value),
1140                     _ => bug!("write_value_to_ptr: invalid ByValPair layout: {:#?}", layout)
1141                 };
1142                 let (a_size, b_size) = (a.size(&self), b.size(&self));
1143                 let a_ptr = ptr;
1144                 let b_offset = a_size.abi_align(b.align(&self));
1145                 let b_ptr = ptr.offset(b_offset.bytes(), &self)?.into();
1146                 // TODO: What about signedess?
1147                 self.memory.write_primval(a_ptr, dest_align, a_val, a_size.bytes(), false)?;
1148                 self.memory.write_primval(b_ptr, dest_align, b_val, b_size.bytes(), false)
1149             }
1150         }
1151     }
1152
1153     pub fn ty_to_primval_kind(&self, ty: Ty<'tcx>) -> EvalResult<'tcx, PrimValKind> {
1154         use syntax::ast::FloatTy;
1155
1156         let kind = match ty.sty {
1157             ty::TyBool => PrimValKind::Bool,
1158             ty::TyChar => PrimValKind::Char,
1159
1160             ty::TyInt(int_ty) => {
1161                 use syntax::ast::IntTy::*;
1162                 let size = match int_ty {
1163                     I8 => 1,
1164                     I16 => 2,
1165                     I32 => 4,
1166                     I64 => 8,
1167                     I128 => 16,
1168                     Isize => self.memory.pointer_size(),
1169                 };
1170                 PrimValKind::from_int_size(size)
1171             }
1172
1173             ty::TyUint(uint_ty) => {
1174                 use syntax::ast::UintTy::*;
1175                 let size = match uint_ty {
1176                     U8 => 1,
1177                     U16 => 2,
1178                     U32 => 4,
1179                     U64 => 8,
1180                     U128 => 16,
1181                     Usize => self.memory.pointer_size(),
1182                 };
1183                 PrimValKind::from_uint_size(size)
1184             }
1185
1186             ty::TyFloat(FloatTy::F32) => PrimValKind::F32,
1187             ty::TyFloat(FloatTy::F64) => PrimValKind::F64,
1188
1189             ty::TyFnPtr(_) => PrimValKind::FnPtr,
1190
1191             ty::TyRef(_, ref tam) |
1192             ty::TyRawPtr(ref tam) if self.type_is_sized(tam.ty) => PrimValKind::Ptr,
1193
1194             ty::TyAdt(def, _) if def.is_box() => PrimValKind::Ptr,
1195
1196             ty::TyAdt(..) => {
1197                 match self.layout_of(ty)?.abi {
1198                     layout::Abi::Scalar(ref scalar) => {
1199                         use rustc::ty::layout::Primitive::*;
1200                         match scalar.value {
1201                             Int(i, false) => PrimValKind::from_uint_size(i.size().bytes()),
1202                             Int(i, true) => PrimValKind::from_int_size(i.size().bytes()),
1203                             F32 => PrimValKind::F32,
1204                             F64 => PrimValKind::F64,
1205                             Pointer => PrimValKind::Ptr,
1206                         }
1207                     }
1208
1209                     _ => return err!(TypeNotPrimitive(ty)),
1210                 }
1211             }
1212
1213             _ => return err!(TypeNotPrimitive(ty)),
1214         };
1215
1216         Ok(kind)
1217     }
1218
1219     fn ensure_valid_value(&self, val: PrimVal, ty: Ty<'tcx>) -> EvalResult<'tcx> {
1220         match ty.sty {
1221             ty::TyBool if val.to_bytes()? > 1 => err!(InvalidBool),
1222
1223             ty::TyChar if ::std::char::from_u32(val.to_bytes()? as u32).is_none() => {
1224                 err!(InvalidChar(val.to_bytes()? as u32 as u128))
1225             }
1226
1227             _ => Ok(()),
1228         }
1229     }
1230
1231     pub fn read_value(&self, ptr: Pointer, align: Align, ty: Ty<'tcx>) -> EvalResult<'tcx, Value> {
1232         if let Some(val) = self.try_read_value(ptr, align, ty)? {
1233             Ok(val)
1234         } else {
1235             bug!("primitive read failed for type: {:?}", ty);
1236         }
1237     }
1238
1239     pub(crate) fn read_ptr(
1240         &self,
1241         ptr: MemoryPointer,
1242         ptr_align: Align,
1243         pointee_ty: Ty<'tcx>,
1244     ) -> EvalResult<'tcx, Value> {
1245         let ptr_size = self.memory.pointer_size();
1246         let p: Pointer = self.memory.read_ptr_sized_unsigned(ptr, ptr_align)?.into();
1247         if self.type_is_sized(pointee_ty) {
1248             Ok(p.to_value())
1249         } else {
1250             trace!("reading fat pointer extra of type {}", pointee_ty);
1251             let extra = ptr.offset(ptr_size, self)?;
1252             match self.tcx.struct_tail(pointee_ty).sty {
1253                 ty::TyDynamic(..) => Ok(p.to_value_with_vtable(
1254                     self.memory.read_ptr_sized_unsigned(extra, ptr_align)?.to_ptr()?,
1255                 )),
1256                 ty::TySlice(..) | ty::TyStr => Ok(
1257                     p.to_value_with_len(self.memory.read_ptr_sized_unsigned(extra, ptr_align)?.to_bytes()? as u64),
1258                 ),
1259                 _ => bug!("unsized primval ptr read from {:?}", pointee_ty),
1260             }
1261         }
1262     }
1263
1264     pub fn try_read_value(&self, ptr: Pointer, ptr_align: Align, ty: Ty<'tcx>) -> EvalResult<'tcx, Option<Value>> {
1265         use syntax::ast::FloatTy;
1266
1267         let ptr = ptr.to_ptr()?;
1268         let val = match ty.sty {
1269             ty::TyBool => {
1270                 let val = self.memory.read_primval(ptr, ptr_align, 1, false)?;
1271                 let val = match val {
1272                     PrimVal::Bytes(0) => false,
1273                     PrimVal::Bytes(1) => true,
1274                     // TODO: This seems a little overeager, should reading at bool type already be insta-UB?
1275                     _ => return err!(InvalidBool),
1276                 };
1277                 PrimVal::from_bool(val)
1278             }
1279             ty::TyChar => {
1280                 let c = self.memory.read_primval(ptr, ptr_align, 4, false)?.to_bytes()? as u32;
1281                 match ::std::char::from_u32(c) {
1282                     Some(ch) => PrimVal::from_char(ch),
1283                     None => return err!(InvalidChar(c as u128)),
1284                 }
1285             }
1286
1287             ty::TyInt(int_ty) => {
1288                 use syntax::ast::IntTy::*;
1289                 let size = match int_ty {
1290                     I8 => 1,
1291                     I16 => 2,
1292                     I32 => 4,
1293                     I64 => 8,
1294                     I128 => 16,
1295                     Isize => self.memory.pointer_size(),
1296                 };
1297                 self.memory.read_primval(ptr, ptr_align, size, true)?
1298             }
1299
1300             ty::TyUint(uint_ty) => {
1301                 use syntax::ast::UintTy::*;
1302                 let size = match uint_ty {
1303                     U8 => 1,
1304                     U16 => 2,
1305                     U32 => 4,
1306                     U64 => 8,
1307                     U128 => 16,
1308                     Usize => self.memory.pointer_size(),
1309                 };
1310                 self.memory.read_primval(ptr, ptr_align, size, false)?
1311             }
1312
1313             ty::TyFloat(FloatTy::F32) => {
1314                 PrimVal::Bytes(self.memory.read_primval(ptr, ptr_align, 4, false)?.to_bytes()?)
1315             }
1316             ty::TyFloat(FloatTy::F64) => {
1317                 PrimVal::Bytes(self.memory.read_primval(ptr, ptr_align, 8, false)?.to_bytes()?)
1318             }
1319
1320             ty::TyFnPtr(_) => self.memory.read_ptr_sized_unsigned(ptr, ptr_align)?,
1321             ty::TyRef(_, ref tam) |
1322             ty::TyRawPtr(ref tam) => return self.read_ptr(ptr, ptr_align, tam.ty).map(Some),
1323
1324             ty::TyAdt(def, _) => {
1325                 if def.is_box() {
1326                     return self.read_ptr(ptr, ptr_align, ty.boxed_ty()).map(Some);
1327                 }
1328
1329                 if let layout::Abi::Scalar(ref scalar) = self.layout_of(ty)?.abi {
1330                     let mut signed = false;
1331                     if let layout::Int(_, s) = scalar.value {
1332                         signed = s;
1333                     }
1334                     let size = scalar.value.size(self).bytes();
1335                     self.memory.read_primval(ptr, ptr_align, size, signed)?
1336                 } else {
1337                     return Ok(None);
1338                 }
1339             }
1340
1341             _ => return Ok(None),
1342         };
1343
1344         Ok(Some(Value::ByVal(val)))
1345     }
1346
1347     pub fn frame(&self) -> &Frame<'tcx> {
1348         self.stack.last().expect("no call frames exist")
1349     }
1350
1351     pub fn frame_mut(&mut self) -> &mut Frame<'tcx> {
1352         self.stack.last_mut().expect("no call frames exist")
1353     }
1354
1355     pub(super) fn mir(&self) -> &'tcx mir::Mir<'tcx> {
1356         self.frame().mir
1357     }
1358
1359     pub fn substs(&self) -> &'tcx Substs<'tcx> {
1360         if let Some(frame) = self.stack.last() {
1361             frame.instance.substs
1362         } else {
1363             Substs::empty()
1364         }
1365     }
1366
1367     fn unsize_into_ptr(
1368         &mut self,
1369         src: Value,
1370         src_ty: Ty<'tcx>,
1371         dest: Place,
1372         dest_ty: Ty<'tcx>,
1373         sty: Ty<'tcx>,
1374         dty: Ty<'tcx>,
1375     ) -> EvalResult<'tcx> {
1376         // A<Struct> -> A<Trait> conversion
1377         let (src_pointee_ty, dest_pointee_ty) = self.tcx.struct_lockstep_tails(sty, dty);
1378
1379         match (&src_pointee_ty.sty, &dest_pointee_ty.sty) {
1380             (&ty::TyArray(_, length), &ty::TySlice(_)) => {
1381                 let ptr = self.into_ptr(src)?;
1382                 // u64 cast is from usize to u64, which is always good
1383                 let valty = ValTy {
1384                     value: ptr.to_value_with_len(length.val.to_const_int().unwrap().to_u64().unwrap() ),
1385                     ty: dest_ty,
1386                 };
1387                 self.write_value(valty, dest)
1388             }
1389             (&ty::TyDynamic(..), &ty::TyDynamic(..)) => {
1390                 // For now, upcasts are limited to changes in marker
1391                 // traits, and hence never actually require an actual
1392                 // change to the vtable.
1393                 let valty = ValTy {
1394                     value: src,
1395                     ty: dest_ty,
1396                 };
1397                 self.write_value(valty, dest)
1398             }
1399             (_, &ty::TyDynamic(ref data, _)) => {
1400                 let trait_ref = data.principal().unwrap().with_self_ty(
1401                     self.tcx,
1402                     src_pointee_ty,
1403                 );
1404                 let trait_ref = self.tcx.erase_regions(&trait_ref);
1405                 let vtable = self.get_vtable(src_pointee_ty, trait_ref)?;
1406                 let ptr = self.into_ptr(src)?;
1407                 let valty = ValTy {
1408                     value: ptr.to_value_with_vtable(vtable),
1409                     ty: dest_ty,
1410                 };
1411                 self.write_value(valty, dest)
1412             }
1413
1414             _ => bug!("invalid unsizing {:?} -> {:?}", src_ty, dest_ty),
1415         }
1416     }
1417
1418     fn unsize_into(
1419         &mut self,
1420         src: Value,
1421         src_layout: TyLayout<'tcx>,
1422         dst: Place,
1423         dst_layout: TyLayout<'tcx>,
1424     ) -> EvalResult<'tcx> {
1425         match (&src_layout.ty.sty, &dst_layout.ty.sty) {
1426             (&ty::TyRef(_, ref s), &ty::TyRef(_, ref d)) |
1427             (&ty::TyRef(_, ref s), &ty::TyRawPtr(ref d)) |
1428             (&ty::TyRawPtr(ref s), &ty::TyRawPtr(ref d)) => {
1429                 self.unsize_into_ptr(src, src_layout.ty, dst, dst_layout.ty, s.ty, d.ty)
1430             }
1431             (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) => {
1432                 assert_eq!(def_a, def_b);
1433                 if def_a.is_box() || def_b.is_box() {
1434                     if !def_a.is_box() || !def_b.is_box() {
1435                         bug!("invalid unsizing between {:?} -> {:?}", src_layout, dst_layout);
1436                     }
1437                     return self.unsize_into_ptr(
1438                         src,
1439                         src_layout.ty,
1440                         dst,
1441                         dst_layout.ty,
1442                         src_layout.ty.boxed_ty(),
1443                         dst_layout.ty.boxed_ty(),
1444                     );
1445                 }
1446
1447                 // unsizing of generic struct with pointer fields
1448                 // Example: `Arc<T>` -> `Arc<Trait>`
1449                 // here we need to increase the size of every &T thin ptr field to a fat ptr
1450                 for i in 0..src_layout.fields.count() {
1451                     let (dst_f_place, dst_field) =
1452                         self.place_field(dst, mir::Field::new(i), dst_layout)?;
1453                     if dst_field.is_zst() {
1454                         continue;
1455                     }
1456                     let (src_f_value, src_field) = match src {
1457                         Value::ByRef(ptr, align) => {
1458                             let src_place = Place::from_primval_ptr(ptr, align);
1459                             let (src_f_place, src_field) =
1460                                 self.place_field(src_place, mir::Field::new(i), src_layout)?;
1461                             (self.read_place(src_f_place)?, src_field)
1462                         }
1463                         Value::ByVal(_) | Value::ByValPair(..) => {
1464                             let src_field = src_layout.field(&self, i)?;
1465                             assert_eq!(src_layout.fields.offset(i).bytes(), 0);
1466                             assert_eq!(src_field.size, src_layout.size);
1467                             (src, src_field)
1468                         }
1469                     };
1470                     if src_field.ty == dst_field.ty {
1471                         self.write_value(ValTy {
1472                             value: src_f_value,
1473                             ty: src_field.ty,
1474                         }, dst_f_place)?;
1475                     } else {
1476                         self.unsize_into(src_f_value, src_field, dst_f_place, dst_field)?;
1477                     }
1478                 }
1479                 Ok(())
1480             }
1481             _ => {
1482                 bug!(
1483                     "unsize_into: invalid conversion: {:?} -> {:?}",
1484                     src_layout,
1485                     dst_layout
1486                 )
1487             }
1488         }
1489     }
1490
1491     pub fn dump_local(&self, place: Place) {
1492         // Debug output
1493         match place {
1494             Place::Local { frame, local } => {
1495                 let mut allocs = Vec::new();
1496                 let mut msg = format!("{:?}", local);
1497                 if frame != self.cur_frame() {
1498                     write!(msg, " ({} frames up)", self.cur_frame() - frame).unwrap();
1499                 }
1500                 write!(msg, ":").unwrap();
1501
1502                 match self.stack[frame].get_local(local) {
1503                     Err(EvalError { kind: EvalErrorKind::DeadLocal, .. }) => {
1504                         write!(msg, " is dead").unwrap();
1505                     }
1506                     Err(err) => {
1507                         panic!("Failed to access local: {:?}", err);
1508                     }
1509                     Ok(Value::ByRef(ptr, align)) => {
1510                         match ptr.into_inner_primval() {
1511                             PrimVal::Ptr(ptr) => {
1512                                 write!(msg, " by align({}) ref:", align.abi()).unwrap();
1513                                 allocs.push(ptr.alloc_id);
1514                             }
1515                             ptr => write!(msg, " integral by ref: {:?}", ptr).unwrap(),
1516                         }
1517                     }
1518                     Ok(Value::ByVal(val)) => {
1519                         write!(msg, " {:?}", val).unwrap();
1520                         if let PrimVal::Ptr(ptr) = val {
1521                             allocs.push(ptr.alloc_id);
1522                         }
1523                     }
1524                     Ok(Value::ByValPair(val1, val2)) => {
1525                         write!(msg, " ({:?}, {:?})", val1, val2).unwrap();
1526                         if let PrimVal::Ptr(ptr) = val1 {
1527                             allocs.push(ptr.alloc_id);
1528                         }
1529                         if let PrimVal::Ptr(ptr) = val2 {
1530                             allocs.push(ptr.alloc_id);
1531                         }
1532                     }
1533                 }
1534
1535                 trace!("{}", msg);
1536                 self.memory.dump_allocs(allocs);
1537             }
1538             Place::Ptr { ptr, align, .. } => {
1539                 match ptr.into_inner_primval() {
1540                     PrimVal::Ptr(ptr) => {
1541                         trace!("by align({}) ref:", align.abi());
1542                         self.memory.dump_alloc(ptr.alloc_id);
1543                     }
1544                     ptr => trace!(" integral by ref: {:?}", ptr),
1545                 }
1546             }
1547         }
1548     }
1549
1550     /// Convenience function to ensure correct usage of locals
1551     pub fn modify_local<F>(&mut self, frame: usize, local: mir::Local, f: F) -> EvalResult<'tcx>
1552     where
1553         F: FnOnce(&mut Self, Value) -> EvalResult<'tcx, Value>,
1554     {
1555         let val = self.stack[frame].get_local(local)?;
1556         let new_val = f(self, val)?;
1557         self.stack[frame].set_local(local, new_val)?;
1558         // FIXME(solson): Run this when setting to Undef? (See previous version of this code.)
1559         // if let Value::ByRef(ptr) = self.stack[frame].get_local(local) {
1560         //     self.memory.deallocate(ptr)?;
1561         // }
1562         Ok(())
1563     }
1564
1565     pub fn report(&self, e: &mut EvalError) {
1566         if let Some(ref mut backtrace) = e.backtrace {
1567             let mut trace_text = "\n\nAn error occurred in miri:\n".to_string();
1568             backtrace.resolve();
1569             write!(trace_text, "backtrace frames: {}\n", backtrace.frames().len()).unwrap();
1570             'frames: for (i, frame) in backtrace.frames().iter().enumerate() {
1571                 if frame.symbols().is_empty() {
1572                     write!(trace_text, "{}: no symbols\n", i).unwrap();
1573                 }
1574                 for symbol in frame.symbols() {
1575                     write!(trace_text, "{}: ", i).unwrap();
1576                     if let Some(name) = symbol.name() {
1577                         write!(trace_text, "{}\n", name).unwrap();
1578                     } else {
1579                         write!(trace_text, "<unknown>\n").unwrap();
1580                     }
1581                     write!(trace_text, "\tat ").unwrap();
1582                     if let Some(file_path) = symbol.filename() {
1583                         write!(trace_text, "{}", file_path.display()).unwrap();
1584                     } else {
1585                         write!(trace_text, "<unknown_file>").unwrap();
1586                     }
1587                     if let Some(line) = symbol.lineno() {
1588                         write!(trace_text, ":{}\n", line).unwrap();
1589                     } else {
1590                         write!(trace_text, "\n").unwrap();
1591                     }
1592                 }
1593             }
1594             error!("{}", trace_text);
1595         }
1596         if let Some(frame) = self.stack().last() {
1597             let block = &frame.mir.basic_blocks()[frame.block];
1598             let span = if frame.stmt < block.statements.len() {
1599                 block.statements[frame.stmt].source_info.span
1600             } else {
1601                 block.terminator().source_info.span
1602             };
1603             let mut err = self.tcx.sess.struct_span_err(span, &e.to_string());
1604             for &Frame { instance, span, .. } in self.stack().iter().rev() {
1605                 if self.tcx.def_key(instance.def_id()).disambiguated_data.data ==
1606                     DefPathData::ClosureExpr
1607                 {
1608                     err.span_note(span, "inside call to closure");
1609                     continue;
1610                 }
1611                 err.span_note(span, &format!("inside call to {}", instance));
1612             }
1613             err.emit();
1614         } else {
1615             self.tcx.sess.err(&e.to_string());
1616         }
1617     }
1618 }
1619
1620 impl<'tcx> Frame<'tcx> {
1621     pub fn get_local(&self, local: mir::Local) -> EvalResult<'tcx, Value> {
1622         // Subtract 1 because we don't store a value for the ReturnPointer, the local with index 0.
1623         self.locals[local.index() - 1].ok_or(EvalErrorKind::DeadLocal.into())
1624     }
1625
1626     fn set_local(&mut self, local: mir::Local, value: Value) -> EvalResult<'tcx> {
1627         // Subtract 1 because we don't store a value for the ReturnPointer, the local with index 0.
1628         match self.locals[local.index() - 1] {
1629             None => err!(DeadLocal),
1630             Some(ref mut local) => {
1631                 *local = value;
1632                 Ok(())
1633             }
1634         }
1635     }
1636
1637     pub fn storage_live(&mut self, local: mir::Local) -> EvalResult<'tcx, Option<Value>> {
1638         trace!("{:?} is now live", local);
1639
1640         let old = self.locals[local.index() - 1];
1641         self.locals[local.index() - 1] = Some(Value::ByVal(PrimVal::Undef)); // StorageLive *always* kills the value that's currently stored
1642         return Ok(old);
1643     }
1644
1645     /// Returns the old value of the local
1646     pub fn storage_dead(&mut self, local: mir::Local) -> EvalResult<'tcx, Option<Value>> {
1647         trace!("{:?} is now dead", local);
1648
1649         let old = self.locals[local.index() - 1];
1650         self.locals[local.index() - 1] = None;
1651         return Ok(old);
1652     }
1653 }
1654
1655 // TODO(solson): Upstream these methods into rustc::ty::layout.
1656
1657 pub fn resolve_drop_in_place<'a, 'tcx>(
1658     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1659     ty: Ty<'tcx>,
1660 ) -> ty::Instance<'tcx> {
1661     let def_id = tcx.require_lang_item(::rustc::middle::lang_items::DropInPlaceFnLangItem);
1662     let substs = tcx.intern_substs(&[Kind::from(ty)]);
1663     ty::Instance::resolve(tcx, ty::ParamEnv::empty(Reveal::All), def_id, substs).unwrap()
1664 }