1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
14 use syntax::source_map::{self, Span, DUMMY_SP};
15 use rustc::hir::def_id::DefId;
16 use rustc::hir::def::Def;
17 use rustc::hir::map::definitions::DefPathData;
19 use rustc::ty::layout::{
20 self, Size, Align, HasDataLayout, LayoutOf, TyLayout
22 use rustc::ty::subst::{Subst, Substs};
23 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
24 use rustc::ty::query::TyCtxtAt;
25 use rustc_data_structures::indexed_vec::IndexVec;
26 use rustc::mir::interpret::{
27 GlobalId, Scalar, FrameInfo, AllocId,
28 EvalResult, EvalErrorKind,
29 truncate, sign_extend,
31 use rustc_data_structures::fx::FxHashMap;
34 Value, Operand, MemPlace, MPlaceTy, Place, PlaceTy, ScalarMaybeUndef,
38 pub struct EvalContext<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'a, 'mir, 'tcx>> {
39 /// Stores the `Machine` instance.
42 /// The results of the type checker, from rustc.
43 pub tcx: TyCtxtAt<'a, 'tcx, 'tcx>,
45 /// Bounds in scope for polymorphic evaluations.
46 pub(crate) param_env: ty::ParamEnv<'tcx>,
48 /// The virtual memory system.
49 pub memory: Memory<'a, 'mir, 'tcx, M>,
51 /// The virtual call stack.
52 pub(crate) stack: Vec<Frame<'mir, 'tcx, M::PointerTag>>,
54 /// A cache for deduplicating vtables
55 pub(super) vtables: FxHashMap<(Ty<'tcx>, ty::PolyExistentialTraitRef<'tcx>), AllocId>,
60 pub struct Frame<'mir, 'tcx: 'mir, Tag=()> {
61 ////////////////////////////////////////////////////////////////////////////////
62 // Function and callsite information
63 ////////////////////////////////////////////////////////////////////////////////
64 /// The MIR for the function called on this frame.
65 pub mir: &'mir mir::Mir<'tcx>,
67 /// The def_id and substs of the current function
68 pub instance: ty::Instance<'tcx>,
70 /// The span of the call site.
71 pub span: source_map::Span,
73 ////////////////////////////////////////////////////////////////////////////////
74 // Return place and locals
75 ////////////////////////////////////////////////////////////////////////////////
76 /// Work to perform when returning from this function
77 pub return_to_block: StackPopCleanup,
79 /// The location where the result of the current stack frame should be written to,
80 /// and its layout in the caller.
81 pub return_place: Option<PlaceTy<'tcx, Tag>>,
83 /// The list of locals for this stack frame, stored in order as
84 /// `[return_ptr, arguments..., variables..., temporaries...]`.
85 /// The locals are stored as `Option<Value>`s.
86 /// `None` represents a local that is currently dead, while a live local
87 /// can either directly contain `Scalar` or refer to some part of an `Allocation`.
88 pub locals: IndexVec<mir::Local, LocalValue<Tag>>,
90 ////////////////////////////////////////////////////////////////////////////////
91 // Current position within the function
92 ////////////////////////////////////////////////////////////////////////////////
93 /// The block that is currently executed (or will be executed after the above call stacks
95 pub block: mir::BasicBlock,
97 /// The index of the currently evaluated statement.
101 #[derive(Clone, Debug, Eq, PartialEq, Hash)]
102 pub enum StackPopCleanup {
103 /// Jump to the next block in the caller, or cause UB if None (that's a function
104 /// that may never return). Also store layout of return place so
105 /// we can validate it at that layout.
106 Goto(Option<mir::BasicBlock>),
107 /// Just do nohing: Used by Main and for the box_alloc hook in miri.
108 /// `cleanup` says whether locals are deallocated. Static computation
109 /// wants them leaked to intern what they need (and just throw away
110 /// the entire `ecx` when it is done).
111 None { cleanup: bool },
114 // State of a local variable
115 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
116 pub enum LocalValue<Tag=(), Id=AllocId> {
118 // Mostly for convenience, we re-use the `Operand` type here.
119 // This is an optimization over just always having a pointer here;
120 // we can thus avoid doing an allocation when the local just stores
121 // immediate values *and* never has its address taken.
122 Live(Operand<Tag, Id>),
125 impl<'tcx, Tag> LocalValue<Tag> {
126 pub fn access(&self) -> EvalResult<'tcx, &Operand<Tag>> {
128 LocalValue::Dead => err!(DeadLocal),
129 LocalValue::Live(ref val) => Ok(val),
133 pub fn access_mut(&mut self) -> EvalResult<'tcx, &mut Operand<Tag>> {
135 LocalValue::Dead => err!(DeadLocal),
136 LocalValue::Live(ref mut val) => Ok(val),
141 impl<'b, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> HasDataLayout
142 for &'b EvalContext<'a, 'mir, 'tcx, M>
145 fn data_layout(&self) -> &layout::TargetDataLayout {
146 &self.tcx.data_layout
150 impl<'c, 'b, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> HasDataLayout
151 for &'c &'b mut EvalContext<'a, 'mir, 'tcx, M>
154 fn data_layout(&self) -> &layout::TargetDataLayout {
155 &self.tcx.data_layout
159 impl<'b, 'a, 'mir, 'tcx, M> layout::HasTyCtxt<'tcx> for &'b EvalContext<'a, 'mir, 'tcx, M>
160 where M: Machine<'a, 'mir, 'tcx>
163 fn tcx<'d>(&'d self) -> TyCtxt<'d, 'tcx, 'tcx> {
168 impl<'c, 'b, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> layout::HasTyCtxt<'tcx>
169 for &'c &'b mut EvalContext<'a, 'mir, 'tcx, M>
172 fn tcx<'d>(&'d self) -> TyCtxt<'d, 'tcx, 'tcx> {
177 impl<'b, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> LayoutOf
178 for &'b EvalContext<'a, 'mir, 'tcx, M>
181 type TyLayout = EvalResult<'tcx, TyLayout<'tcx>>;
184 fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
185 self.tcx.layout_of(self.param_env.and(ty))
186 .map_err(|layout| EvalErrorKind::Layout(layout).into())
190 impl<'c, 'b, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> LayoutOf
191 for &'c &'b mut EvalContext<'a, 'mir, 'tcx, M>
194 type TyLayout = EvalResult<'tcx, TyLayout<'tcx>>;
197 fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
198 (&**self).layout_of(ty)
202 impl<'a, 'mir, 'tcx: 'mir, M: Machine<'a, 'mir, 'tcx>> EvalContext<'a, 'mir, 'tcx, M> {
204 tcx: TyCtxtAt<'a, 'tcx, 'tcx>,
205 param_env: ty::ParamEnv<'tcx>,
212 memory: Memory::new(tcx),
214 vtables: FxHashMap::default(),
219 pub fn memory(&self) -> &Memory<'a, 'mir, 'tcx, M> {
224 pub fn memory_mut(&mut self) -> &mut Memory<'a, 'mir, 'tcx, M> {
229 pub fn stack(&self) -> &[Frame<'mir, 'tcx, M::PointerTag>] {
234 pub fn cur_frame(&self) -> usize {
235 assert!(self.stack.len() > 0);
240 pub fn frame(&self) -> &Frame<'mir, 'tcx, M::PointerTag> {
241 self.stack.last().expect("no call frames exist")
245 pub fn frame_mut(&mut self) -> &mut Frame<'mir, 'tcx, M::PointerTag> {
246 self.stack.last_mut().expect("no call frames exist")
250 pub(super) fn mir(&self) -> &'mir mir::Mir<'tcx> {
254 pub fn substs(&self) -> &'tcx Substs<'tcx> {
255 if let Some(frame) = self.stack.last() {
256 frame.instance.substs
262 pub(super) fn resolve(
265 substs: &'tcx Substs<'tcx>
266 ) -> EvalResult<'tcx, ty::Instance<'tcx>> {
267 trace!("resolve: {:?}, {:#?}", def_id, substs);
268 trace!("substs: {:#?}", self.substs());
269 trace!("param_env: {:#?}", self.param_env);
270 let substs = self.tcx.subst_and_normalize_erasing_regions(
275 ty::Instance::resolve(
280 ).ok_or_else(|| EvalErrorKind::TooGeneric.into())
283 pub fn type_is_sized(&self, ty: Ty<'tcx>) -> bool {
284 ty.is_sized(self.tcx, self.param_env)
287 pub fn type_is_freeze(&self, ty: Ty<'tcx>) -> bool {
288 ty.is_freeze(*self.tcx, self.param_env, DUMMY_SP)
293 instance: ty::InstanceDef<'tcx>,
294 ) -> EvalResult<'tcx, &'tcx mir::Mir<'tcx>> {
295 // do not continue if typeck errors occurred (can only occur in local crate)
296 let did = instance.def_id();
298 && self.tcx.has_typeck_tables(did)
299 && self.tcx.typeck_tables_of(did).tainted_by_errors
301 return err!(TypeckError);
303 trace!("load mir {:?}", instance);
305 ty::InstanceDef::Item(def_id) => {
306 self.tcx.maybe_optimized_mir(def_id).ok_or_else(||
307 EvalErrorKind::NoMirFor(self.tcx.item_path_str(def_id)).into()
310 _ => Ok(self.tcx.instance_mir(instance)),
314 pub fn monomorphize<T: TypeFoldable<'tcx> + Subst<'tcx>>(
317 substs: &'tcx Substs<'tcx>
319 // miri doesn't care about lifetimes, and will choke on some crazy ones
320 // let's simply get rid of them
321 let substituted = t.subst(*self.tcx, substs);
322 self.tcx.normalize_erasing_regions(ty::ParamEnv::reveal_all(), substituted)
325 pub fn layout_of_local(
327 frame: &Frame<'mir, 'tcx, M::PointerTag>,
329 ) -> EvalResult<'tcx, TyLayout<'tcx>> {
330 let local_ty = frame.mir.local_decls[local].ty;
331 let local_ty = self.monomorphize(local_ty, frame.instance.substs);
332 self.layout_of(local_ty)
335 pub fn str_to_value(&mut self, s: &str) -> EvalResult<'tcx, Value<M::PointerTag>> {
336 let ptr = self.memory.allocate_static_bytes(s.as_bytes());
337 Ok(Value::new_slice(Scalar::Ptr(ptr), s.len() as u64, self.tcx.tcx))
340 /// Return the actual dynamic size and alignment of the place at the given type.
341 /// Only the "meta" (metadata) part of the place matters.
342 /// This can fail to provide an answer for extern types.
343 pub(super) fn size_and_align_of(
345 metadata: Option<Scalar<M::PointerTag>>,
346 layout: TyLayout<'tcx>,
347 ) -> EvalResult<'tcx, Option<(Size, Align)>> {
348 if !layout.is_unsized() {
349 return Ok(Some(layout.size_and_align()));
351 match layout.ty.sty {
352 ty::Adt(..) | ty::Tuple(..) => {
353 // First get the size of all statically known fields.
354 // Don't use type_of::sizing_type_of because that expects t to be sized,
355 // and it also rounds up to alignment, which we want to avoid,
356 // as the unsized field's alignment could be smaller.
357 assert!(!layout.ty.is_simd());
358 trace!("DST layout: {:?}", layout);
360 let sized_size = layout.fields.offset(layout.fields.count() - 1);
361 let sized_align = layout.align;
363 "DST {} statically sized prefix size: {:?} align: {:?}",
369 // Recurse to get the size of the dynamically sized field (must be
370 // the last field). Can't have foreign types here, how would we
371 // adjust alignment and size for them?
372 let field = layout.field(self, layout.fields.count() - 1)?;
373 let (unsized_size, unsized_align) = self.size_and_align_of(metadata, field)?
374 .expect("Fields cannot be extern types");
376 // FIXME (#26403, #27023): We should be adding padding
377 // to `sized_size` (to accommodate the `unsized_align`
378 // required of the unsized field that follows) before
379 // summing it with `sized_size`. (Note that since #26403
380 // is unfixed, we do not yet add the necessary padding
381 // here. But this is where the add would go.)
383 // Return the sum of sizes and max of aligns.
384 let size = sized_size + unsized_size;
386 // Choose max of two known alignments (combined value must
387 // be aligned according to more restrictive of the two).
388 let align = sized_align.max(unsized_align);
390 // Issue #27023: must add any necessary padding to `size`
391 // (to make it a multiple of `align`) before returning it.
393 // Namely, the returned size should be, in C notation:
395 // `size + ((size & (align-1)) ? align : 0)`
397 // emulated via the semi-standard fast bit trick:
399 // `(size + (align-1)) & -align`
401 Ok(Some((size.abi_align(align), align)))
404 let vtable = metadata.expect("dyn trait fat ptr must have vtable").to_ptr()?;
405 // the second entry in the vtable is the dynamic size of the object.
406 Ok(Some(self.read_size_and_align_from_vtable(vtable)?))
409 ty::Slice(_) | ty::Str => {
410 let len = metadata.expect("slice fat ptr must have vtable").to_usize(self)?;
411 let (elem_size, align) = layout.field(self, 0)?.size_and_align();
412 Ok(Some((elem_size * len, align)))
419 _ => bug!("size_and_align_of::<{:?}> not supported", layout.ty),
423 pub fn size_and_align_of_mplace(
425 mplace: MPlaceTy<'tcx, M::PointerTag>
426 ) -> EvalResult<'tcx, Option<(Size, Align)>> {
427 self.size_and_align_of(mplace.meta, mplace.layout)
430 pub fn push_stack_frame(
432 instance: ty::Instance<'tcx>,
433 span: source_map::Span,
434 mir: &'mir mir::Mir<'tcx>,
435 return_place: Option<PlaceTy<'tcx, M::PointerTag>>,
436 return_to_block: StackPopCleanup,
437 ) -> EvalResult<'tcx> {
438 if self.stack.len() > 1 { // FIXME should be "> 0", printing topmost frame crashes rustc...
439 debug!("PAUSING({}) {}", self.cur_frame(), self.frame().instance);
441 ::log_settings::settings().indentation += 1;
443 // first push a stack frame so we have access to the local substs
444 self.stack.push(Frame {
446 block: mir::START_BLOCK,
449 // empty local array, we fill it in below, after we are inside the stack frame and
450 // all methods actually know about the frame
451 locals: IndexVec::new(),
457 // don't allocate at all for trivial constants
458 if mir.local_decls.len() > 1 {
459 // We put some marker value into the locals that we later want to initialize.
460 // This can be anything except for LocalValue::Dead -- because *that* is the
461 // value we use for things that we know are initially dead.
463 LocalValue::Live(Operand::Immediate(Value::Scalar(ScalarMaybeUndef::Undef)));
464 let mut locals = IndexVec::from_elem(dummy, &mir.local_decls);
465 // Return place is handled specially by the `eval_place` functions, and the
466 // entry in `locals` should never be used. Make it dead, to be sure.
467 locals[mir::RETURN_PLACE] = LocalValue::Dead;
468 // Now mark those locals as dead that we do not want to initialize
469 match self.tcx.describe_def(instance.def_id()) {
470 // statics and constants don't have `Storage*` statements, no need to look for them
471 Some(Def::Static(..)) | Some(Def::Const(..)) | Some(Def::AssociatedConst(..)) => {},
473 trace!("push_stack_frame: {:?}: num_bbs: {}", span, mir.basic_blocks().len());
474 for block in mir.basic_blocks() {
475 for stmt in block.statements.iter() {
476 use rustc::mir::StatementKind::{StorageDead, StorageLive};
479 StorageDead(local) => {
480 locals[local] = LocalValue::Dead;
488 // Finally, properly initialize all those that still have the dummy value
489 for (local, decl) in locals.iter_mut().zip(mir.local_decls.iter()) {
491 LocalValue::Live(_) => {
492 // This needs to be peoperly initialized.
493 let layout = self.layout_of(self.monomorphize(decl.ty, instance.substs))?;
494 *local = LocalValue::Live(self.uninit_operand(layout)?);
496 LocalValue::Dead => {
502 self.frame_mut().locals = locals;
505 if self.stack.len() > 1 { // FIXME no check should be needed, but some instances ICE
506 debug!("ENTERING({}) {}", self.cur_frame(), self.frame().instance);
509 if self.stack.len() > self.tcx.sess.const_eval_stack_frame_limit {
510 err!(StackFrameLimitReached)
516 pub(super) fn pop_stack_frame(&mut self) -> EvalResult<'tcx> {
517 if self.stack.len() > 1 { // FIXME no check should be needed, but some instances ICE
518 debug!("LEAVING({}) {}", self.cur_frame(), self.frame().instance);
520 ::log_settings::settings().indentation -= 1;
521 let frame = self.stack.pop().expect(
522 "tried to pop a stack frame, but there were none",
524 match frame.return_to_block {
525 StackPopCleanup::Goto(block) => {
526 self.goto_block(block)?;
528 StackPopCleanup::None { cleanup } => {
530 // Leak the locals. Also skip validation, this is only used by
531 // static/const computation which does its own (stronger) final
537 // Deallocate all locals that are backed by an allocation.
538 for local in frame.locals {
539 self.deallocate_local(local)?;
541 // Validate the return value.
542 if let Some(return_place) = frame.return_place {
543 if M::enforce_validity(self) {
544 // Data got changed, better make sure it matches the type!
545 // It is still possible that the return place held invalid data while
546 // the function is running, but that's okay because nobody could have
547 // accessed that same data from the "outside" to observe any broken
548 // invariant -- that is, unless a function somehow has a ptr to
549 // its return place... but the way MIR is currently generated, the
550 // return place is always a local and then this cannot happen.
551 self.validate_operand(
552 self.place_to_op(return_place)?,
559 // Uh, that shouln't happen... the function did not intend to return
560 return err!(Unreachable);
563 if self.stack.len() > 1 { // FIXME should be "> 0", printing topmost frame crashes rustc...
564 debug!("CONTINUING({}) {}", self.cur_frame(), self.frame().instance);
570 /// Mark a storage as live, killing the previous content and returning it.
571 /// Remember to deallocate that!
575 ) -> EvalResult<'tcx, LocalValue<M::PointerTag>> {
576 assert!(local != mir::RETURN_PLACE, "Cannot make return place live");
577 trace!("{:?} is now live", local);
579 let layout = self.layout_of_local(self.frame(), local)?;
580 let init = LocalValue::Live(self.uninit_operand(layout)?);
581 // StorageLive *always* kills the value that's currently stored
582 Ok(mem::replace(&mut self.frame_mut().locals[local], init))
585 /// Returns the old value of the local.
586 /// Remember to deallocate that!
587 pub fn storage_dead(&mut self, local: mir::Local) -> LocalValue<M::PointerTag> {
588 assert!(local != mir::RETURN_PLACE, "Cannot make return place dead");
589 trace!("{:?} is now dead", local);
591 mem::replace(&mut self.frame_mut().locals[local], LocalValue::Dead)
594 pub(super) fn deallocate_local(
596 local: LocalValue<M::PointerTag>,
597 ) -> EvalResult<'tcx> {
598 // FIXME: should we tell the user that there was a local which was never written to?
599 if let LocalValue::Live(Operand::Indirect(MemPlace { ptr, .. })) = local {
600 trace!("deallocating local");
601 let ptr = ptr.to_ptr()?;
602 self.memory.dump_alloc(ptr.alloc_id);
603 self.memory.deallocate_local(ptr)?;
608 pub fn const_eval(&self, gid: GlobalId<'tcx>) -> EvalResult<'tcx, &'tcx ty::Const<'tcx>> {
609 let param_env = if self.tcx.is_static(gid.instance.def_id()).is_some() {
610 ty::ParamEnv::reveal_all()
614 self.tcx.const_eval(param_env.and(gid))
615 .map_err(|err| EvalErrorKind::ReferencedConstant(err).into())
618 pub fn dump_place(&self, place: Place<M::PointerTag>) {
620 if !log_enabled!(::log::Level::Trace) {
624 Place::Local { frame, local } => {
625 let mut allocs = Vec::new();
626 let mut msg = format!("{:?}", local);
627 if frame != self.cur_frame() {
628 write!(msg, " ({} frames up)", self.cur_frame() - frame).unwrap();
630 write!(msg, ":").unwrap();
632 match self.stack[frame].locals[local].access() {
634 if let EvalErrorKind::DeadLocal = err.kind {
635 write!(msg, " is dead").unwrap();
637 panic!("Failed to access local: {:?}", err);
640 Ok(Operand::Indirect(mplace)) => {
641 let (ptr, align) = mplace.to_scalar_ptr_align();
643 Scalar::Ptr(ptr) => {
644 write!(msg, " by align({}) ref:", align.abi()).unwrap();
645 allocs.push(ptr.alloc_id);
647 ptr => write!(msg, " by integral ref: {:?}", ptr).unwrap(),
650 Ok(Operand::Immediate(Value::Scalar(val))) => {
651 write!(msg, " {:?}", val).unwrap();
652 if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val {
653 allocs.push(ptr.alloc_id);
656 Ok(Operand::Immediate(Value::ScalarPair(val1, val2))) => {
657 write!(msg, " ({:?}, {:?})", val1, val2).unwrap();
658 if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val1 {
659 allocs.push(ptr.alloc_id);
661 if let ScalarMaybeUndef::Scalar(Scalar::Ptr(ptr)) = val2 {
662 allocs.push(ptr.alloc_id);
668 self.memory.dump_allocs(allocs);
670 Place::Ptr(mplace) => {
672 Scalar::Ptr(ptr) => {
673 trace!("by align({}) ref:", mplace.align.abi());
674 self.memory.dump_alloc(ptr.alloc_id);
676 ptr => trace!(" integral by ref: {:?}", ptr),
682 pub fn generate_stacktrace(&self, explicit_span: Option<Span>) -> (Vec<FrameInfo>, Span) {
683 let mut last_span = None;
684 let mut frames = Vec::new();
685 // skip 1 because the last frame is just the environment of the constant
686 for &Frame { instance, span, mir, block, stmt, .. } in self.stack().iter().skip(1).rev() {
687 // make sure we don't emit frames that are duplicates of the previous
688 if explicit_span == Some(span) {
689 last_span = Some(span);
692 if let Some(last) = last_span {
697 last_span = Some(span);
699 let location = if self.tcx.def_key(instance.def_id()).disambiguated_data.data
700 == DefPathData::ClosureExpr
706 let block = &mir.basic_blocks()[block];
707 let source_info = if stmt < block.statements.len() {
708 block.statements[stmt].source_info
710 block.terminator().source_info
712 let lint_root = match mir.source_scope_local_data {
713 mir::ClearCrossCrate::Set(ref ivs) => Some(ivs[source_info.scope].lint_root),
714 mir::ClearCrossCrate::Clear => None,
716 frames.push(FrameInfo { span, location, lint_root });
718 trace!("generate stacktrace: {:#?}, {:?}", frames, explicit_span);
719 (frames, self.tcx.span)
723 pub fn sign_extend(&self, value: u128, ty: TyLayout<'_>) -> u128 {
724 assert!(ty.abi.is_signed());
725 sign_extend(value, ty.size)
729 pub fn truncate(&self, value: u128, ty: TyLayout<'_>) -> u128 {
730 truncate(value, ty.size)