src/interpreter/mod.rs

   1 use rustc::middle::const_val;
   2 use rustc::hir::def_id::DefId;
   3 use rustc::mir::mir_map::MirMap;
   4 use rustc::mir::repr as mir;
   5 use rustc::traits::Reveal;
   6 use rustc::ty::layout::{self, Layout, Size};
   7 use rustc::ty::subst::{self, Subst, Substs};
   8 use rustc::ty::{self, Ty, TyCtxt};
   9 use rustc::util::nodemap::DefIdMap;
  10 use rustc_data_structures::indexed_vec::Idx;
  11 use std::cell::RefCell;
  12 use std::ops::Deref;
  13 use std::rc::Rc;
  14 use std::iter;
  15 use syntax::codemap::{self, DUMMY_SP};
  16
  17 use error::{EvalError, EvalResult};
  18 use memory::{Memory, Pointer};
  19 use primval::{self, PrimVal};
  20
  21 use std::collections::HashMap;
  22
  23 mod step;
  24 mod terminator;
  25
  26 pub struct EvalContext<'a, 'tcx: 'a> {
  27     /// The results of the type checker, from rustc.
  28     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  29
  30     /// A mapping from NodeIds to Mir, from rustc. Only contains MIR for crate-local items.
  31     mir_map: &'a MirMap<'tcx>,
  32
  33     /// A local cache from DefIds to Mir for non-crate-local items.
  34     mir_cache: RefCell<DefIdMap<Rc<mir::Mir<'tcx>>>>,
  35
  36     /// The virtual memory system.
  37     memory: Memory<'a, 'tcx>,
  38
  39     /// Precomputed statics, constants and promoteds.
  40     statics: HashMap<ConstantId<'tcx>, Pointer>,
  41
  42     /// The virtual call stack.
  43     stack: Vec<Frame<'a, 'tcx>>,
  44
  45     /// The maximum number of stack frames allowed
  46     stack_limit: usize,
  47 }
  48
  49 /// A stack frame.
  50 pub struct Frame<'a, 'tcx: 'a> {
  51     ////////////////////////////////////////////////////////////////////////////////
  52     // Function and callsite information
  53     ////////////////////////////////////////////////////////////////////////////////
  54
  55     /// The MIR for the function called on this frame.
  56     pub mir: CachedMir<'a, 'tcx>,
  57
  58     /// The def_id of the current function.
  59     pub def_id: DefId,
  60
  61     /// type substitutions for the current function invocation.
  62     pub substs: &'tcx Substs<'tcx>,
  63
  64     /// The span of the call site.
  65     pub span: codemap::Span,
  66
  67     ////////////////////////////////////////////////////////////////////////////////
  68     // Return pointer and local allocations
  69     ////////////////////////////////////////////////////////////////////////////////
  70
  71     /// A pointer for writing the return value of the current call if it's not a diverging call.
  72     pub return_ptr: Option<Pointer>,
  73
  74     /// The list of locals for the current function, stored in order as
  75     /// `[arguments..., variables..., temporaries...]`. The variables begin at `self.var_offset`
  76     /// and the temporaries at `self.temp_offset`.
  77     pub locals: Vec<Pointer>,
  78
  79     /// The offset of the first variable in `self.locals`.
  80     pub var_offset: usize,
  81
  82     /// The offset of the first temporary in `self.locals`.
  83     pub temp_offset: usize,
  84
  85     ////////////////////////////////////////////////////////////////////////////////
  86     // Current position within the function
  87     ////////////////////////////////////////////////////////////////////////////////
  88
  89     /// The block that is currently executed (or will be executed after the above call stacks
  90     /// return).
  91     pub block: mir::BasicBlock,
  92
  93     /// The index of the currently evaluated statment.
  94     pub stmt: usize,
  95 }
  96
  97 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  98 struct Lvalue {
  99     ptr: Pointer,
 100     extra: LvalueExtra,
 101 }
 102
 103 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
 104 enum LvalueExtra {
 105     None,
 106     Length(u64),
 107     // TODO(solson): Vtable(memory::AllocId),
 108     DowncastVariant(usize),
 109 }
 110
 111 #[derive(Clone)]
 112 pub enum CachedMir<'mir, 'tcx: 'mir> {
 113     Ref(&'mir mir::Mir<'tcx>),
 114     Owned(Rc<mir::Mir<'tcx>>)
 115 }
 116
 117 #[derive(Clone, Debug, Eq, PartialEq, Hash)]
 118 /// Uniquely identifies a specific constant or static
 119 struct ConstantId<'tcx> {
 120     /// the def id of the constant/static or in case of promoteds, the def id of the function they belong to
 121     def_id: DefId,
 122     /// In case of statics and constants this is `Substs::empty()`, so only promoteds and associated
 123     /// constants actually have something useful here. We could special case statics and constants,
 124     /// but that would only require more branching when working with constants, and not bring any
 125     /// real benefits.
 126     substs: &'tcx Substs<'tcx>,
 127     kind: ConstantKind,
 128 }
 129
 130 #[derive(Clone, Debug, Eq, PartialEq, Hash)]
 131 enum ConstantKind {
 132     Promoted(mir::Promoted),
 133     /// Statics, constants and associated constants
 134     Global,
 135 }
 136
 137 impl<'a, 'tcx> EvalContext<'a, 'tcx> {
 138     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir_map: &'a MirMap<'tcx>, memory_size: usize, stack_limit: usize) -> Self {
 139         EvalContext {
 140             tcx: tcx,
 141             mir_map: mir_map,
 142             mir_cache: RefCell::new(DefIdMap()),
 143             memory: Memory::new(&tcx.data_layout, memory_size),
 144             statics: HashMap::new(),
 145             stack: Vec::new(),
 146             stack_limit: stack_limit,
 147         }
 148     }
 149
 150     pub fn alloc_ret_ptr(&mut self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> EvalResult<'tcx, Pointer> {
 151         let size = self.type_size_with_substs(ty, substs);
 152         let align = self.type_align_with_substs(ty, substs);
 153         self.memory.allocate(size, align)
 154     }
 155
 156     pub fn memory(&self) -> &Memory<'a, 'tcx> {
 157         &self.memory
 158     }
 159
 160     pub fn memory_mut(&mut self) -> &mut Memory<'a, 'tcx> {
 161         &mut self.memory
 162     }
 163
 164     pub fn stack(&self) -> &[Frame<'a, 'tcx>] {
 165         &self.stack
 166     }
 167
 168     // TODO(solson): Try making const_to_primval instead.
 169     fn const_to_ptr(&mut self, const_val: &const_val::ConstVal) -> EvalResult<'tcx, Pointer> {
 170         use rustc::middle::const_val::ConstVal::*;
 171         use rustc_const_math::{ConstInt, ConstIsize, ConstUsize, ConstFloat};
 172         macro_rules! i2p {
 173             ($i:ident, $n:expr) => {{
 174                 let ptr = self.memory.allocate($n, $n)?;
 175                 self.memory.write_int(ptr, $i as i64, $n)?;
 176                 Ok(ptr)
 177             }}
 178         }
 179         match *const_val {
 180             Float(ConstFloat::F32(f)) => {
 181                 let ptr = self.memory.allocate(4, 4)?;
 182                 self.memory.write_f32(ptr, f)?;
 183                 Ok(ptr)
 184             },
 185             Float(ConstFloat::F64(f)) => {
 186                 let ptr = self.memory.allocate(8, 8)?;
 187                 self.memory.write_f64(ptr, f)?;
 188                 Ok(ptr)
 189             },
 190             Float(ConstFloat::FInfer{..}) => unreachable!(),
 191             Integral(ConstInt::Infer(_)) => unreachable!(),
 192             Integral(ConstInt::InferSigned(_)) => unreachable!(),
 193             Integral(ConstInt::I8(i)) => i2p!(i, 1),
 194             Integral(ConstInt::U8(i)) => i2p!(i, 1),
 195             Integral(ConstInt::Isize(ConstIsize::Is16(i))) |
 196             Integral(ConstInt::I16(i)) => i2p!(i, 2),
 197             Integral(ConstInt::Usize(ConstUsize::Us16(i))) |
 198             Integral(ConstInt::U16(i)) => i2p!(i, 2),
 199             Integral(ConstInt::Isize(ConstIsize::Is32(i))) |
 200             Integral(ConstInt::I32(i)) => i2p!(i, 4),
 201             Integral(ConstInt::Usize(ConstUsize::Us32(i))) |
 202             Integral(ConstInt::U32(i)) => i2p!(i, 4),
 203             Integral(ConstInt::Isize(ConstIsize::Is64(i))) |
 204             Integral(ConstInt::I64(i)) => i2p!(i, 8),
 205             Integral(ConstInt::Usize(ConstUsize::Us64(i))) |
 206             Integral(ConstInt::U64(i)) => i2p!(i, 8),
 207             Str(ref s) => {
 208                 let psize = self.memory.pointer_size();
 209                 let static_ptr = self.memory.allocate(s.len(), 1)?;
 210                 let ptr = self.memory.allocate(psize * 2, psize)?;
 211                 self.memory.write_bytes(static_ptr, s.as_bytes())?;
 212                 self.memory.write_ptr(ptr, static_ptr)?;
 213                 self.memory.write_usize(ptr.offset(psize as isize), s.len() as u64)?;
 214                 Ok(ptr)
 215             }
 216             ByteStr(ref bs) => {
 217                 let psize = self.memory.pointer_size();
 218                 let static_ptr = self.memory.allocate(bs.len(), 1)?;
 219                 let ptr = self.memory.allocate(psize, psize)?;
 220                 self.memory.write_bytes(static_ptr, bs)?;
 221                 self.memory.write_ptr(ptr, static_ptr)?;
 222                 Ok(ptr)
 223             }
 224             Bool(b) => {
 225                 let ptr = self.memory.allocate(1, 1)?;
 226                 self.memory.write_bool(ptr, b)?;
 227                 Ok(ptr)
 228             }
 229             Char(c) => {
 230                 let ptr = self.memory.allocate(4, 4)?;
 231                 self.memory.write_uint(ptr, c as u64, 4)?;
 232                 Ok(ptr)
 233             },
 234             Struct(_node_id)  => unimplemented!(),
 235             Tuple(_node_id)   => unimplemented!(),
 236             Function(_def_id) => unimplemented!(),
 237             Array(_, _)       => unimplemented!(),
 238             Repeat(_, _)      => unimplemented!(),
 239             Dummy             => unimplemented!(),
 240         }
 241     }
 242
 243     fn type_is_sized(&self, ty: Ty<'tcx>) -> bool {
 244         ty.is_sized(self.tcx, &self.tcx.empty_parameter_environment(), DUMMY_SP)
 245     }
 246
 247     pub fn load_mir(&self, def_id: DefId) -> CachedMir<'a, 'tcx> {
 248         if def_id.is_local() {
 249             CachedMir::Ref(self.mir_map.map.get(&def_id).unwrap())
 250         } else {
 251             let mut mir_cache = self.mir_cache.borrow_mut();
 252             if let Some(mir) = mir_cache.get(&def_id) {
 253                 return CachedMir::Owned(mir.clone());
 254             }
 255
 256             let cs = &self.tcx.sess.cstore;
 257             let mir = cs.maybe_get_item_mir(self.tcx, def_id).unwrap_or_else(|| {
 258                 panic!("no mir for `{}`", self.tcx.item_path_str(def_id));
 259             });
 260             let cached = Rc::new(mir);
 261             mir_cache.insert(def_id, cached.clone());
 262             CachedMir::Owned(cached)
 263         }
 264     }
 265
 266     pub fn monomorphize(&self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
 267         let substituted = ty.subst(self.tcx, substs);
 268         self.tcx.normalize_associated_type(&substituted)
 269     }
 270
 271     fn type_size(&self, ty: Ty<'tcx>) -> usize {
 272         self.type_size_with_substs(ty, self.substs())
 273     }
 274
 275     fn type_align(&self, ty: Ty<'tcx>) -> usize {
 276         self.type_align_with_substs(ty, self.substs())
 277     }
 278
 279     fn type_size_with_substs(&self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> usize {
 280         self.type_layout_with_substs(ty, substs).size(&self.tcx.data_layout).bytes() as usize
 281     }
 282
 283     fn type_align_with_substs(&self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> usize {
 284         self.type_layout_with_substs(ty, substs).align(&self.tcx.data_layout).abi() as usize
 285     }
 286
 287     fn type_layout(&self, ty: Ty<'tcx>) -> &'tcx Layout {
 288         self.type_layout_with_substs(ty, self.substs())
 289     }
 290
 291     fn type_layout_with_substs(&self, ty: Ty<'tcx>, substs: &'tcx Substs<'tcx>) -> &'tcx Layout {
 292         // TODO(solson): Is this inefficient? Needs investigation.
 293         let ty = self.monomorphize(ty, substs);
 294
 295         self.tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
 296             // TODO(solson): Report this error properly.
 297             ty.layout(&infcx).unwrap()
 298         })
 299     }
 300
 301     pub fn push_stack_frame(
 302         &mut self,
 303         def_id: DefId,
 304         span: codemap::Span,
 305         mir: CachedMir<'a, 'tcx>,
 306         substs: &'tcx Substs<'tcx>,
 307         return_ptr: Option<Pointer>,
 308     ) -> EvalResult<'tcx, ()> {
 309         let arg_tys = mir.arg_decls.iter().map(|a| a.ty);
 310         let var_tys = mir.var_decls.iter().map(|v| v.ty);
 311         let temp_tys = mir.temp_decls.iter().map(|t| t.ty);
 312
 313         let num_args = mir.arg_decls.len();
 314         let num_vars = mir.var_decls.len();
 315
 316         ::log_settings::settings().indentation += 1;
 317
 318         let locals: EvalResult<'tcx, Vec<Pointer>> = arg_tys.chain(var_tys).chain(temp_tys).map(|ty| {
 319             let size = self.type_size_with_substs(ty, substs);
 320             let align = self.type_align_with_substs(ty, substs);
 321             self.memory.allocate(size, align)
 322         }).collect();
 323
 324         self.stack.push(Frame {
 325             mir: mir.clone(),
 326             block: mir::START_BLOCK,
 327             return_ptr: return_ptr,
 328             locals: locals?,
 329             var_offset: num_args,
 330             temp_offset: num_args + num_vars,
 331             span: span,
 332             def_id: def_id,
 333             substs: substs,
 334             stmt: 0,
 335         });
 336         if self.stack.len() > self.stack_limit {
 337             Err(EvalError::StackFrameLimitReached)
 338         } else {
 339             Ok(())
 340         }
 341     }
 342
 343     fn pop_stack_frame(&mut self) {
 344         ::log_settings::settings().indentation -= 1;
 345         let _frame = self.stack.pop().expect("tried to pop a stack frame, but there were none");
 346         // TODO(solson): Deallocate local variables.
 347     }
 348
 349     /// Applies the binary operation `op` to the two operands and writes a tuple of the result
 350     /// and a boolean signifying the potential overflow to the destination.
 351     fn intrinsic_with_overflow(
 352         &mut self,
 353         op: mir::BinOp,
 354         left: &mir::Operand<'tcx>,
 355         right: &mir::Operand<'tcx>,
 356         dest: Pointer,
 357         dest_layout: &'tcx Layout,
 358     ) -> EvalResult<'tcx, ()> {
 359         use rustc::ty::layout::Layout::*;
 360         let tup_layout = match *dest_layout {
 361             Univariant { ref variant, .. } => variant,
 362             _ => panic!("checked bin op returns something other than a tuple"),
 363         };
 364
 365         let overflowed = self.intrinsic_overflowing(op, left, right, dest)?;
 366         let offset = tup_layout.field_offset(1).bytes() as isize;
 367         self.memory.write_bool(dest.offset(offset), overflowed)
 368     }
 369
 370     /// Applies the binary operation `op` to the arguments and writes the result to the destination.
 371     /// Returns `true` if the operation overflowed.
 372     fn intrinsic_overflowing(
 373         &mut self,
 374         op: mir::BinOp,
 375         left: &mir::Operand<'tcx>,
 376         right: &mir::Operand<'tcx>,
 377         dest: Pointer,
 378     ) -> EvalResult<'tcx, bool> {
 379         let left_ptr = self.eval_operand(left)?;
 380         let left_ty = self.operand_ty(left);
 381         let left_val = self.read_primval(left_ptr, left_ty)?;
 382
 383         let right_ptr = self.eval_operand(right)?;
 384         let right_ty = self.operand_ty(right);
 385         let right_val = self.read_primval(right_ptr, right_ty)?;
 386
 387         let (val, overflow) = primval::binary_op(op, left_val, right_val)?;
 388         self.memory.write_primval(dest, val)?;
 389         Ok(overflow)
 390     }
 391
 392     fn assign_fields<I: IntoIterator<Item = u64>>(
 393         &mut self,
 394         dest: Pointer,
 395         offsets: I,
 396         operands: &[mir::Operand<'tcx>],
 397     ) -> EvalResult<'tcx, ()> {
 398         for (offset, operand) in offsets.into_iter().zip(operands) {
 399             let src = self.eval_operand(operand)?;
 400             let src_ty = self.operand_ty(operand);
 401             let field_dest = dest.offset(offset as isize);
 402             self.move_(src, field_dest, src_ty)?;
 403         }
 404         Ok(())
 405     }
 406
 407     fn eval_assignment(&mut self, lvalue: &mir::Lvalue<'tcx>, rvalue: &mir::Rvalue<'tcx>)
 408         -> EvalResult<'tcx, ()>
 409     {
 410         let dest = self.eval_lvalue(lvalue)?.to_ptr();
 411         let dest_ty = self.lvalue_ty(lvalue);
 412         let dest_layout = self.type_layout(dest_ty);
 413
 414         use rustc::mir::repr::Rvalue::*;
 415         match *rvalue {
 416             Use(ref operand) => {
 417                 let src = self.eval_operand(operand)?;
 418                 self.move_(src, dest, dest_ty)?;
 419             }
 420
 421             BinaryOp(bin_op, ref left, ref right) => {
 422                 // ignore overflow bit, rustc inserts check branches for us
 423                 self.intrinsic_overflowing(bin_op, left, right, dest)?;
 424             }
 425
 426             CheckedBinaryOp(bin_op, ref left, ref right) => {
 427                 self.intrinsic_with_overflow(bin_op, left, right, dest, dest_layout)?;
 428             }
 429
 430             UnaryOp(un_op, ref operand) => {
 431                 let ptr = self.eval_operand(operand)?;
 432                 let ty = self.operand_ty(operand);
 433                 let val = self.read_primval(ptr, ty)?;
 434                 self.memory.write_primval(dest, primval::unary_op(un_op, val)?)?;
 435             }
 436
 437             Aggregate(ref kind, ref operands) => {
 438                 use rustc::ty::layout::Layout::*;
 439                 match *dest_layout {
 440                     Univariant { ref variant, .. } => {
 441                         let offsets = iter::once(0)
 442                             .chain(variant.offset_after_field.iter().map(|s| s.bytes()));
 443                         self.assign_fields(dest, offsets, operands)?;
 444                     }
 445
 446                     Array { .. } => {
 447                         let elem_size = match dest_ty.sty {
 448                             ty::TyArray(elem_ty, _) => self.type_size(elem_ty) as u64,
 449                             _ => panic!("tried to assign {:?} to non-array type {:?}",
 450                                         kind, dest_ty),
 451                         };
 452                         let offsets = (0..).map(|i| i * elem_size);
 453                         self.assign_fields(dest, offsets, operands)?;
 454                     }
 455
 456                     General { discr, ref variants, .. } => {
 457                         if let mir::AggregateKind::Adt(adt_def, variant, _) = *kind {
 458                             let discr_val = adt_def.variants[variant].disr_val.to_u64_unchecked();
 459                             let discr_size = discr.size().bytes() as usize;
 460                             self.memory.write_uint(dest, discr_val, discr_size)?;
 461
 462                             let offsets = variants[variant].offset_after_field.iter()
 463                                 .map(|s| s.bytes());
 464                             self.assign_fields(dest, offsets, operands)?;
 465                         } else {
 466                             panic!("tried to assign {:?} to Layout::General", kind);
 467                         }
 468                     }
 469
 470                     RawNullablePointer { nndiscr, .. } => {
 471                         if let mir::AggregateKind::Adt(_, variant, _) = *kind {
 472                             if nndiscr == variant as u64 {
 473                                 assert_eq!(operands.len(), 1);
 474                                 let operand = &operands[0];
 475                                 let src = self.eval_operand(operand)?;
 476                                 let src_ty = self.operand_ty(operand);
 477                                 self.move_(src, dest, src_ty)?;
 478                             } else {
 479                                 assert_eq!(operands.len(), 0);
 480                                 self.memory.write_isize(dest, 0)?;
 481                             }
 482                         } else {
 483                             panic!("tried to assign {:?} to Layout::RawNullablePointer", kind);
 484                         }
 485                     }
 486
 487                     StructWrappedNullablePointer { nndiscr, ref nonnull, ref discrfield } => {
 488                         if let mir::AggregateKind::Adt(_, variant, _) = *kind {
 489                             if nndiscr == variant as u64 {
 490                                 let offsets = iter::once(0)
 491                                     .chain(nonnull.offset_after_field.iter().map(|s| s.bytes()));
 492                                 try!(self.assign_fields(dest, offsets, operands));
 493                             } else {
 494                                 assert_eq!(operands.len(), 0);
 495                                 let offset = self.nonnull_offset(dest_ty, nndiscr, discrfield)?;
 496                                 let dest = dest.offset(offset.bytes() as isize);
 497                                 try!(self.memory.write_isize(dest, 0));
 498                             }
 499                         } else {
 500                             panic!("tried to assign {:?} to Layout::RawNullablePointer", kind);
 501                         }
 502                     }
 503
 504                     CEnum { discr, signed, .. } => {
 505                         assert_eq!(operands.len(), 0);
 506                         if let mir::AggregateKind::Adt(adt_def, variant, _) = *kind {
 507                             let val = adt_def.variants[variant].disr_val.to_u64_unchecked();
 508                             let size = discr.size().bytes() as usize;
 509
 510                             if signed {
 511                                 self.memory.write_int(dest, val as i64, size)?;
 512                             } else {
 513                                 self.memory.write_uint(dest, val, size)?;
 514                             }
 515                         } else {
 516                             panic!("tried to assign {:?} to Layout::CEnum", kind);
 517                         }
 518                     }
 519
 520                     _ => return Err(EvalError::Unimplemented(format!("can't handle destination layout {:?} when assigning {:?}", dest_layout, kind))),
 521                 }
 522             }
 523
 524             Repeat(ref operand, _) => {
 525                 let (elem_size, elem_align, length) = match dest_ty.sty {
 526                     ty::TyArray(elem_ty, n) => (self.type_size(elem_ty), self.type_align(elem_ty), n),
 527                     _ => panic!("tried to assign array-repeat to non-array type {:?}", dest_ty),
 528                 };
 529
 530                 let src = self.eval_operand(operand)?;
 531                 for i in 0..length {
 532                     let elem_dest = dest.offset((i * elem_size) as isize);
 533                     self.memory.copy(src, elem_dest, elem_size, elem_align)?;
 534                 }
 535             }
 536
 537             Len(ref lvalue) => {
 538                 let src = self.eval_lvalue(lvalue)?;
 539                 let ty = self.lvalue_ty(lvalue);
 540                 let len = match ty.sty {
 541                     ty::TyArray(_, n) => n as u64,
 542                     ty::TySlice(_) => if let LvalueExtra::Length(n) = src.extra {
 543                         n
 544                     } else {
 545                         panic!("Rvalue::Len of a slice given non-slice pointer: {:?}", src);
 546                     },
 547                     _ => panic!("Rvalue::Len expected array or slice, got {:?}", ty),
 548                 };
 549                 self.memory.write_usize(dest, len)?;
 550             }
 551
 552             Ref(_, _, ref lvalue) => {
 553                 let lv = self.eval_lvalue(lvalue)?;
 554                 self.memory.write_ptr(dest, lv.ptr)?;
 555                 match lv.extra {
 556                     LvalueExtra::None => {},
 557                     LvalueExtra::Length(len) => {
 558                         let len_ptr = dest.offset(self.memory.pointer_size() as isize);
 559                         self.memory.write_usize(len_ptr, len)?;
 560                     }
 561                     LvalueExtra::DowncastVariant(..) =>
 562                         panic!("attempted to take a reference to an enum downcast lvalue"),
 563                 }
 564             }
 565
 566             Box(ty) => {
 567                 let size = self.type_size(ty);
 568                 let align = self.type_align(ty);
 569                 let ptr = self.memory.allocate(size, align)?;
 570                 self.memory.write_ptr(dest, ptr)?;
 571             }
 572
 573             Cast(kind, ref operand, dest_ty) => {
 574                 use rustc::mir::repr::CastKind::*;
 575                 match kind {
 576                     Unsize => {
 577                         let src = self.eval_operand(operand)?;
 578                         let src_ty = self.operand_ty(operand);
 579                         self.move_(src, dest, src_ty)?;
 580                         let src_pointee_ty = pointee_type(src_ty).unwrap();
 581                         let dest_pointee_ty = pointee_type(dest_ty).unwrap();
 582
 583                         match (&src_pointee_ty.sty, &dest_pointee_ty.sty) {
 584                             (&ty::TyArray(_, length), &ty::TySlice(_)) => {
 585                                 let len_ptr = dest.offset(self.memory.pointer_size() as isize);
 586                                 self.memory.write_usize(len_ptr, length as u64)?;
 587                             }
 588
 589                             _ => return Err(EvalError::Unimplemented(format!("can't handle cast: {:?}", rvalue))),
 590                         }
 591                     }
 592
 593                     Misc => {
 594                         let src = self.eval_operand(operand)?;
 595                         let src_ty = self.operand_ty(operand);
 596                         // FIXME(solson): Wrong for almost everything.
 597                         warn!("misc cast from {:?} to {:?}", src_ty, dest_ty);
 598                         let dest_size = self.type_size(dest_ty);
 599                         let src_size = self.type_size(src_ty);
 600                         let dest_align = self.type_align(dest_ty);
 601
 602                         // Hack to support fat pointer -> thin pointer casts to keep tests for
 603                         // other things passing for now.
 604                         let is_fat_ptr_cast = pointee_type(src_ty).map_or(false, |ty| !self.type_is_sized(ty));
 605
 606                         if dest_size == src_size || is_fat_ptr_cast {
 607                             self.memory.copy(src, dest, dest_size, dest_align)?;
 608                         } else {
 609                             return Err(EvalError::Unimplemented(format!("can't handle cast: {:?}", rvalue)));
 610                         }
 611                     }
 612
 613                     ReifyFnPointer => match self.operand_ty(operand).sty {
 614                         ty::TyFnDef(def_id, substs, fn_ty) => {
 615                             let fn_ptr = self.memory.create_fn_ptr(def_id, substs, fn_ty);
 616                             self.memory.write_ptr(dest, fn_ptr)?;
 617                         },
 618                         ref other => panic!("reify fn pointer on {:?}", other),
 619                     },
 620
 621                     UnsafeFnPointer => match dest_ty.sty {
 622                         ty::TyFnPtr(unsafe_fn_ty) => {
 623                             let src = self.eval_operand(operand)?;
 624                             let ptr = self.memory.read_ptr(src)?;
 625                             let fn_def = self.memory.get_fn(ptr.alloc_id)?;
 626                             let fn_ptr = self.memory.create_fn_ptr(fn_def.def_id, fn_def.substs, unsafe_fn_ty);
 627                             self.memory.write_ptr(dest, fn_ptr)?;
 628                         },
 629                         ref other => panic!("fn to unsafe fn cast on {:?}", other),
 630                     },
 631                 }
 632             }
 633
 634             InlineAsm { .. } => unimplemented!(),
 635         }
 636
 637         Ok(())
 638     }
 639
 640     fn nonnull_offset(&self, ty: Ty<'tcx>, nndiscr: u64, discrfield: &[u32]) -> EvalResult<'tcx, Size> {
 641         // Skip the constant 0 at the start meant for LLVM GEP.
 642         let mut path = discrfield.iter().skip(1).map(|&i| i as usize);
 643
 644         // Handle the field index for the outer non-null variant.
 645         let inner_ty = match ty.sty {
 646             ty::TyEnum(adt_def, substs) => {
 647                 let variant = &adt_def.variants[nndiscr as usize];
 648                 let index = path.next().unwrap();
 649                 let field = &variant.fields[index];
 650                 field.ty(self.tcx, substs)
 651             }
 652             _ => panic!(
 653                 "non-enum for StructWrappedNullablePointer: {}",
 654                 ty,
 655             ),
 656         };
 657
 658         self.field_path_offset(inner_ty, path)
 659     }
 660
 661     fn field_path_offset<I: Iterator<Item = usize>>(&self, mut ty: Ty<'tcx>, path: I) -> EvalResult<'tcx, Size> {
 662         let mut offset = Size::from_bytes(0);
 663
 664         // Skip the initial 0 intended for LLVM GEP.
 665         for field_index in path {
 666             let field_offset = self.get_field_offset(ty, field_index)?;
 667             ty = self.get_field_ty(ty, field_index)?;
 668             offset = offset.checked_add(field_offset, &self.tcx.data_layout).unwrap();
 669         }
 670
 671         Ok(offset)
 672     }
 673
 674     fn get_field_ty(&self, ty: Ty<'tcx>, field_index: usize) -> EvalResult<'tcx, Ty<'tcx>> {
 675         match ty.sty {
 676             ty::TyStruct(adt_def, substs) => {
 677                 Ok(adt_def.struct_variant().fields[field_index].ty(self.tcx, substs))
 678             }
 679
 680             ty::TyRef(_, ty::TypeAndMut { ty, .. }) |
 681             ty::TyRawPtr(ty::TypeAndMut { ty, .. }) |
 682             ty::TyBox(ty) => {
 683                 assert_eq!(field_index, 0);
 684                 Ok(ty)
 685             }
 686             _ => Err(EvalError::Unimplemented(format!("can't handle type: {:?}", ty))),
 687         }
 688     }
 689
 690     fn get_field_offset(&self, ty: Ty<'tcx>, field_index: usize) -> EvalResult<'tcx, Size> {
 691         let layout = self.type_layout(ty);
 692
 693         use rustc::ty::layout::Layout::*;
 694         match *layout {
 695             Univariant { .. } => {
 696                 assert_eq!(field_index, 0);
 697                 Ok(Size::from_bytes(0))
 698             }
 699             FatPointer { .. } => {
 700                 let bytes = layout::FAT_PTR_ADDR * self.memory.pointer_size();
 701                 Ok(Size::from_bytes(bytes as u64))
 702             }
 703             _ => Err(EvalError::Unimplemented(format!("can't handle type: {:?}, with layout: {:?}", ty, layout))),
 704         }
 705     }
 706
 707     fn eval_operand(&mut self, op: &mir::Operand<'tcx>) -> EvalResult<'tcx, Pointer> {
 708         use rustc::mir::repr::Operand::*;
 709         match *op {
 710             Consume(ref lvalue) => Ok(self.eval_lvalue(lvalue)?.to_ptr()),
 711             Constant(mir::Constant { ref literal, ty, .. }) => {
 712                 use rustc::mir::repr::Literal::*;
 713                 match *literal {
 714                     Value { ref value } => Ok(self.const_to_ptr(value)?),
 715                     Item { def_id, substs } => {
 716                         if let ty::TyFnDef(..) = ty.sty {
 717                             // function items are zero sized
 718                             Ok(self.memory.allocate(0, 0)?)
 719                         } else {
 720                             let cid = ConstantId {
 721                                 def_id: def_id,
 722                                 substs: substs,
 723                                 kind: ConstantKind::Global,
 724                             };
 725                             Ok(*self.statics.get(&cid).expect("static should have been cached (rvalue)"))
 726                         }
 727                     },
 728                     Promoted { index } => {
 729                         let cid = ConstantId {
 730                             def_id: self.frame().def_id,
 731                             substs: self.substs(),
 732                             kind: ConstantKind::Promoted(index),
 733                         };
 734                         Ok(*self.statics.get(&cid).expect("a promoted constant hasn't been precomputed"))
 735                     },
 736                 }
 737             }
 738         }
 739     }
 740
 741     fn eval_lvalue(&mut self, lvalue: &mir::Lvalue<'tcx>) -> EvalResult<'tcx, Lvalue> {
 742         use rustc::mir::repr::Lvalue::*;
 743         let ptr = match *lvalue {
 744             ReturnPointer => self.frame().return_ptr
 745                 .expect("ReturnPointer used in a function with no return value"),
 746             Arg(i) => self.frame().locals[i.index()],
 747             Var(i) => self.frame().locals[self.frame().var_offset + i.index()],
 748             Temp(i) => self.frame().locals[self.frame().temp_offset + i.index()],
 749
 750             Static(def_id) => {
 751                 let substs = subst::Substs::empty(self.tcx);
 752                 let cid = ConstantId {
 753                     def_id: def_id,
 754                     substs: substs,
 755                     kind: ConstantKind::Global,
 756                 };
 757                 *self.statics.get(&cid).expect("static should have been cached (lvalue)")
 758             },
 759
 760             Projection(ref proj) => {
 761                 let base = self.eval_lvalue(&proj.base)?;
 762                 let base_ty = self.lvalue_ty(&proj.base);
 763                 let base_layout = self.type_layout(base_ty);
 764
 765                 use rustc::mir::repr::ProjectionElem::*;
 766                 match proj.elem {
 767                     Field(field, _) => {
 768                         use rustc::ty::layout::Layout::*;
 769                         let variant = match *base_layout {
 770                             Univariant { ref variant, .. } => variant,
 771                             General { ref variants, .. } => {
 772                                 if let LvalueExtra::DowncastVariant(variant_idx) = base.extra {
 773                                     &variants[variant_idx]
 774                                 } else {
 775                                     panic!("field access on enum had no variant index");
 776                                 }
 777                             }
 778                             RawNullablePointer { .. } => {
 779                                 assert_eq!(field.index(), 0);
 780                                 return Ok(base);
 781                             }
 782                             StructWrappedNullablePointer { ref nonnull, .. } => nonnull,
 783                             _ => panic!("field access on non-product type: {:?}", base_layout),
 784                         };
 785
 786                         let offset = variant.field_offset(field.index()).bytes();
 787                         base.ptr.offset(offset as isize)
 788                     },
 789
 790                     Downcast(_, variant) => {
 791                         use rustc::ty::layout::Layout::*;
 792                         match *base_layout {
 793                             General { discr, .. } => {
 794                                 return Ok(Lvalue {
 795                                     ptr: base.ptr.offset(discr.size().bytes() as isize),
 796                                     extra: LvalueExtra::DowncastVariant(variant),
 797                                 });
 798                             }
 799                             RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
 800                                 return Ok(base);
 801                             }
 802                             _ => panic!("variant downcast on non-aggregate: {:?}", base_layout),
 803                         }
 804                     },
 805
 806                     Deref => {
 807                         let pointee_ty = pointee_type(base_ty).expect("Deref of non-pointer");
 808                         let ptr = self.memory.read_ptr(base.ptr)?;
 809                         let extra = match pointee_ty.sty {
 810                             ty::TySlice(_) | ty::TyStr => {
 811                                 let len_ptr = base.ptr.offset(self.memory.pointer_size() as isize);
 812                                 let len = self.memory.read_usize(len_ptr)?;
 813                                 LvalueExtra::Length(len)
 814                             }
 815                             ty::TyTrait(_) => unimplemented!(),
 816                             _ => LvalueExtra::None,
 817                         };
 818                         return Ok(Lvalue { ptr: ptr, extra: extra });
 819                     }
 820
 821                     Index(ref operand) => {
 822                         let elem_size = match base_ty.sty {
 823                             ty::TyArray(elem_ty, _) |
 824                             ty::TySlice(elem_ty) => self.type_size(elem_ty),
 825                             _ => panic!("indexing expected an array or slice, got {:?}", base_ty),
 826                         };
 827                         let n_ptr = self.eval_operand(operand)?;
 828                         let n = self.memory.read_usize(n_ptr)?;
 829                         base.ptr.offset(n as isize * elem_size as isize)
 830                     }
 831
 832                     ConstantIndex { .. } => unimplemented!(),
 833                     Subslice { .. } => unimplemented!(),
 834                 }
 835             }
 836         };
 837
 838         Ok(Lvalue { ptr: ptr, extra: LvalueExtra::None })
 839     }
 840
 841     fn lvalue_ty(&self, lvalue: &mir::Lvalue<'tcx>) -> Ty<'tcx> {
 842         self.monomorphize(lvalue.ty(&self.mir(), self.tcx).to_ty(self.tcx), self.substs())
 843     }
 844
 845     fn operand_ty(&self, operand: &mir::Operand<'tcx>) -> Ty<'tcx> {
 846         self.monomorphize(operand.ty(&self.mir(), self.tcx), self.substs())
 847     }
 848
 849     fn move_(&mut self, src: Pointer, dest: Pointer, ty: Ty<'tcx>) -> EvalResult<'tcx, ()> {
 850         let size = self.type_size(ty);
 851         let align = self.type_align(ty);
 852         self.memory.copy(src, dest, size, align)?;
 853         Ok(())
 854     }
 855
 856     pub fn read_primval(&mut self, ptr: Pointer, ty: Ty<'tcx>) -> EvalResult<'tcx, PrimVal> {
 857         use syntax::ast::{IntTy, UintTy, FloatTy};
 858         let val = match (self.memory.pointer_size(), &ty.sty) {
 859             (_, &ty::TyBool)              => PrimVal::Bool(self.memory.read_bool(ptr)?),
 860             (_, &ty::TyChar)              => {
 861                 let c = self.memory.read_uint(ptr, 4)? as u32;
 862                 match ::std::char::from_u32(c) {
 863                     Some(ch) => PrimVal::Char(ch),
 864                     None => return Err(EvalError::InvalidChar(c)),
 865                 }
 866             }
 867             (_, &ty::TyInt(IntTy::I8))    => PrimVal::I8(self.memory.read_int(ptr, 1)? as i8),
 868             (2, &ty::TyInt(IntTy::Is)) |
 869             (_, &ty::TyInt(IntTy::I16))   => PrimVal::I16(self.memory.read_int(ptr, 2)? as i16),
 870             (4, &ty::TyInt(IntTy::Is)) |
 871             (_, &ty::TyInt(IntTy::I32))   => PrimVal::I32(self.memory.read_int(ptr, 4)? as i32),
 872             (8, &ty::TyInt(IntTy::Is)) |
 873             (_, &ty::TyInt(IntTy::I64))   => PrimVal::I64(self.memory.read_int(ptr, 8)? as i64),
 874             (_, &ty::TyUint(UintTy::U8))  => PrimVal::U8(self.memory.read_uint(ptr, 1)? as u8),
 875             (2, &ty::TyUint(UintTy::Us)) |
 876             (_, &ty::TyUint(UintTy::U16)) => PrimVal::U16(self.memory.read_uint(ptr, 2)? as u16),
 877             (4, &ty::TyUint(UintTy::Us)) |
 878             (_, &ty::TyUint(UintTy::U32)) => PrimVal::U32(self.memory.read_uint(ptr, 4)? as u32),
 879             (8, &ty::TyUint(UintTy::Us)) |
 880             (_, &ty::TyUint(UintTy::U64)) => PrimVal::U64(self.memory.read_uint(ptr, 8)? as u64),
 881
 882             (_, &ty::TyFloat(FloatTy::F32)) => PrimVal::F32(self.memory.read_f32(ptr)?),
 883             (_, &ty::TyFloat(FloatTy::F64)) => PrimVal::F64(self.memory.read_f64(ptr)?),
 884
 885             (_, &ty::TyFnDef(def_id, substs, fn_ty)) => {
 886                 PrimVal::FnPtr(self.memory.create_fn_ptr(def_id, substs, fn_ty))
 887             },
 888             (_, &ty::TyFnPtr(_)) => self.memory.read_ptr(ptr).map(PrimVal::FnPtr)?,
 889             (_, &ty::TyRef(_, ty::TypeAndMut { ty, .. })) |
 890             (_, &ty::TyRawPtr(ty::TypeAndMut { ty, .. })) => {
 891                 if self.type_is_sized(ty) {
 892                     match self.memory.read_ptr(ptr) {
 893                         Ok(p) => PrimVal::AbstractPtr(p),
 894                         Err(EvalError::ReadBytesAsPointer) => {
 895                             PrimVal::IntegerPtr(self.memory.read_usize(ptr)?)
 896                         }
 897                         Err(e) => return Err(e),
 898                     }
 899                 } else {
 900                     return Err(EvalError::Unimplemented(format!("unimplemented: primitive read of fat pointer type: {:?}", ty)));
 901                 }
 902             }
 903
 904             _ => panic!("primitive read of non-primitive type: {:?}", ty),
 905         };
 906         Ok(val)
 907     }
 908
 909     fn frame(&self) -> &Frame<'a, 'tcx> {
 910         self.stack.last().expect("no call frames exist")
 911     }
 912
 913     pub fn frame_mut(&mut self) -> &mut Frame<'a, 'tcx> {
 914         self.stack.last_mut().expect("no call frames exist")
 915     }
 916
 917     fn mir(&self) -> CachedMir<'a, 'tcx> {
 918         self.frame().mir.clone()
 919     }
 920
 921     fn substs(&self) -> &'tcx Substs<'tcx> {
 922         self.frame().substs
 923     }
 924 }
 925
 926 fn pointee_type(ptr_ty: ty::Ty) -> Option<ty::Ty> {
 927     match ptr_ty.sty {
 928         ty::TyRef(_, ty::TypeAndMut { ty, .. }) |
 929         ty::TyRawPtr(ty::TypeAndMut { ty, .. }) |
 930         ty::TyBox(ty) => {
 931             Some(ty)
 932         }
 933         _ => None,
 934     }
 935 }
 936
 937 impl Lvalue {
 938     fn to_ptr(self) -> Pointer {
 939         assert_eq!(self.extra, LvalueExtra::None);
 940         self.ptr
 941     }
 942 }
 943
 944 impl<'mir, 'tcx: 'mir> Deref for CachedMir<'mir, 'tcx> {
 945     type Target = mir::Mir<'tcx>;
 946     fn deref(&self) -> &mir::Mir<'tcx> {
 947         match *self {
 948             CachedMir::Ref(r) => r,
 949             CachedMir::Owned(ref rc) => rc,
 950         }
 951     }
 952 }
 953
 954 pub fn eval_main<'a, 'tcx: 'a>(
 955     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 956     mir_map: &'a MirMap<'tcx>,
 957     def_id: DefId,
 958     memory_size: usize,
 959     step_limit: u64,
 960     stack_limit: usize,
 961 ) {
 962     let mir = mir_map.map.get(&def_id).expect("no mir for main function");
 963     let mut ecx = EvalContext::new(tcx, mir_map, memory_size, stack_limit);
 964     let substs = subst::Substs::empty(tcx);
 965     let return_ptr = ecx.alloc_ret_ptr(mir.return_ty, substs)
 966         .expect("should at least be able to allocate space for the main function's return value");
 967
 968     ecx.push_stack_frame(def_id, mir.span, CachedMir::Ref(mir), substs, Some(return_ptr))
 969         .expect("could not allocate first stack frame");
 970
 971     if mir.arg_decls.len() == 2 {
 972         // start function
 973         let ptr_size = ecx.memory().pointer_size();
 974         let nargs = ecx.memory_mut().allocate(ptr_size, ptr_size).expect("can't allocate memory for nargs");
 975         ecx.memory_mut().write_usize(nargs, 0).unwrap();
 976         let args = ecx.memory_mut().allocate(ptr_size, ptr_size).expect("can't allocate memory for arg pointer");
 977         ecx.memory_mut().write_usize(args, 0).unwrap();
 978         ecx.frame_mut().locals[0] = nargs;
 979         ecx.frame_mut().locals[1] = args;
 980     }
 981
 982     for _ in 0..step_limit {
 983         match ecx.step() {
 984             Ok(true) => {}
 985             Ok(false) => return,
 986             // FIXME: diverging functions can end up here in some future miri
 987             Err(e) => {
 988                 report(tcx, &ecx, e);
 989                 return;
 990             }
 991         }
 992     }
 993     report(tcx, &ecx, EvalError::ExecutionTimeLimitReached);
 994 }
 995
 996 fn report(tcx: TyCtxt, ecx: &EvalContext, e: EvalError) {
 997     let frame = ecx.stack().last().expect("stackframe was empty");
 998     let block = &frame.mir.basic_blocks()[frame.block];
 999     let span = if frame.stmt < block.statements.len() {
1000         block.statements[frame.stmt].source_info.span
1001     } else {
1002         block.terminator().source_info.span
1003     };
1004     let mut err = tcx.sess.struct_span_err(span, &e.to_string());
1005     for &Frame { def_id, substs, span, .. } in ecx.stack().iter().rev() {
1006         // FIXME(solson): Find a way to do this without this Display impl hack.
1007         use rustc::util::ppaux;
1008         use std::fmt;
1009         struct Instance<'tcx>(DefId, &'tcx subst::Substs<'tcx>);
1010         impl<'tcx> fmt::Display for Instance<'tcx> {
1011             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1012                 ppaux::parameterized(f, self.1, self.0, ppaux::Ns::Value, &[])
1013             }
1014         }
1015         err.span_note(span, &format!("inside call to {}", Instance(def_id, substs)));
1016     }
1017     err.emit();
1018 }
1019
1020 pub fn run_mir_passes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir_map: &mut MirMap<'tcx>) {
1021     let mut passes = ::rustc::mir::transform::Passes::new();
1022     passes.push_hook(Box::new(::rustc_mir::transform::dump_mir::DumpMir));
1023     passes.push_pass(Box::new(::rustc_mir::transform::no_landing_pads::NoLandingPads));
1024     passes.push_pass(Box::new(::rustc_mir::transform::simplify_cfg::SimplifyCfg::new("no-landing-pads")));
1025
1026     passes.push_pass(Box::new(::rustc_mir::transform::erase_regions::EraseRegions));
1027
1028     passes.push_pass(Box::new(::rustc_borrowck::ElaborateDrops));
1029     passes.push_pass(Box::new(::rustc_mir::transform::no_landing_pads::NoLandingPads));
1030     passes.push_pass(Box::new(::rustc_mir::transform::simplify_cfg::SimplifyCfg::new("elaborate-drops")));
1031     passes.push_pass(Box::new(::rustc_mir::transform::dump_mir::Marker("PreMiri")));
1032
1033     passes.run_passes(tcx, mir_map);
1034 }
1035
1036 // TODO(solson): Upstream these methods into rustc::ty::layout.
1037
1038 trait IntegerExt {
1039     fn size(self) -> Size;
1040 }
1041
1042 impl IntegerExt for layout::Integer {
1043     fn size(self) -> Size {
1044         use rustc::ty::layout::Integer::*;
1045         match self {
1046             I1 | I8 => Size::from_bits(8),
1047             I16 => Size::from_bits(16),
1048             I32 => Size::from_bits(32),
1049             I64 => Size::from_bits(64),
1050         }
1051     }
1052 }
1053
1054 trait StructExt {
1055     fn field_offset(&self, index: usize) -> Size;
1056 }
1057
1058 impl StructExt for layout::Struct {
1059     fn field_offset(&self, index: usize) -> Size {
1060         if index == 0 {
1061             Size::from_bytes(0)
1062         } else {
1063             self.offset_after_field[index - 1]
1064         }
1065     }
1066 }